[POJ 3694] Network

#include <algorithm> ?#include <bitset> ?#include <cctype> ?#include <cerrno> ?#include <clocale> ?#include <cmath> ?#include <complex> ?#include <cstdio> ?#include <cstdlib> ?#include <cstring> ?#include <ctime> ?#include <deque> ?#include <exception> ?#include <fstream> ?#include <functional> ?#include <limits> ?#include <list> ?#include <map> ?#include <iomanip> ?#include <ios> ?#include <iosfwd> ?#include <iostream> ?#include <istream> ?#include <ostream> ?#include <queue> ?#include <set> ?#include <sstream> ?#include <stdexcept> ?#include <streambuf> ?#include <string> ?#include <utility> ?#include <vector> ?#include <cwchar> ?#include <cwctype> ?#include <stack> ?#include <limits.h>using namespace std;#define MAXN 100010#define MAXM 200010#define MAXLOG 20struct edge{ ???????int to,nxt;} e[MAXM << 2],ec[MAXM << 2];int i,j,n,m,ans,tot,ctot,cnt,u,v,timer,Lca,x,y,q,TC;int head[MAXN],chead[MAXN],low[MAXN],dfn[MAXN],belong[MAXN],fa[MAXN],depth[MAXN];int anc[MAXN][MAXLOG];bool is_bridge[MAXM << 1],visited[MAXN];inline void addedge(int u,int v){ ???????tot++; ???????e[tot] = (edge){v,head[u]}; ???????head[u] = tot;}inline void addcedge(int u,int v){ ???????ctot++; ???????ec[ctot] = (edge){v,chead[u]}; ???????chead[u] = ctot;} inline void tarjan(int u,int t){ ???????int i,v; ???????dfn[u] = low[u] = ++timer; ???????visited[u] = true; ???????for (i = head[u]; i; i = e[i].nxt) ???????{ ???????????????v = e[i].to; ???????????????if (!visited[v]) ???????????????{ ???????????????????????tarjan(v,i); ???????????????????????if (low[v] > dfn[u]) is_bridge[i] = is_bridge[i ^ 1] = true; ???????????????????????low[u] = min(low[u],low[v]); ???????????????} else if (i != (t ^ 1)) low[u] = min(low[u],dfn[v]); ???????}}inline void dfs(int u){ ???????int i,v; ???????belong[u] = cnt; ???????for (i = head[u]; i; i = e[i].nxt) ???????{ ???????????????v = e[i].to; ???????????????if (belong[v] || is_bridge[i]) continue; ???????????????dfs(v); ???????}}inline void lca_init(){ ???????int i,j,u,v; ???????queue< int > q; ???????while (!q.empty()) q.pop(); ???????q.push(1); ???????depth[1] = 1; ???????while (!q.empty()) ???????{ ???????????????u = q.front(); ???????????????q.pop(); ???????????????for (i = chead[u]; i; i = ec[i].nxt) ???????????????{ ???????????????????????v = ec[i].to; ???????????????????????if (depth[v]) continue; ???????????????????????depth[v] = depth[u] + 1; ???????????????????????anc[v][0] = u; ???????????????????????for (j = 1; j < MAXLOG; j++) ???????????????????????????????anc[v][j] = anc[anc[v][j - 1]][j - 1]; ???????????????????????q.push(v); ???????????????} ???????}}inline int lca(int x,int y){ ???????int i,t; ???????if (depth[x] > depth[y]) swap(x,y); ???????t = depth[y] - depth[x]; ???????for (i = 0; i < MAXLOG; i++) ???????{ ???????????????if (t & (1 << i)) ???????????????????????y = anc[y][i]; ???????} ???????if (x == y) return x; ???????for (i = MAXLOG - 1; i >= 0; i--) ???????{ ???????????????if (anc[x][i] != anc[y][i]) ???????????????{ ???????????????????????x = anc[x][i]; ???????????????????????y = anc[y][i]; ???????????????????????} ???????????} ????????return anc[x][0];}inline int get_root(int x){ ???????if (fa[x] == x) return x; ???????return fa[x] = get_root(fa[x]);}int main() { ???????????????while (scanf("%d%d",&n,&m) && (n || m)) ???????{ ???????????????tot = 1; ???????????????ctot = cnt = timer = 0; ???????????????for (i = 1; i <= n; i++) ????????????????{ ???????????????????????head[i] = 0; ???????????????????????chead[i] = 0; ???????????????????????dfn[i] = 0; ???????????????????????low[i] = 0; ???????????????????????belong[i] = 0; ???????????????????????visited[i] = false; ???????????????????????fa[i] = i; ???????????????????????depth[i] = 0; ???????????????} ???????????????for (i = 1; i <= 2 * m + 1; i++) is_bridge[i] = false; ???????????????for (i = 1; i <= m; i++) ???????????????{ ???????????????????????scanf("%d%d",&u,&v); ???????????????????????addedge(u,v); ???????????????????????addedge(v,u); ???????????????????} ???????????????????????for (i = 1; i <= n; i++) ???????????????????{ ???????????????????????if (!dfn[i]) ???????????????????????????????tarjan(i,0); ???????????????????????} ???????????????????????????for (i = 1; i <= n; i++) ???????????????{ ???????????????????????if (!belong[i]) ???????????????????????{ ???????????????????????????????cnt++; ???????????????????????????????dfs(i); ???????????????????????} ???????????????} ???????????????for (u = 1; u <= n; u++) ???????????????{ ???????????????????????for (j = head[u]; j; j = e[j].nxt) ???????????????????????{ ???????????????????????????????v = e[j].to; ???????????????????????????????if (belong[u] != belong[v]) ???????????????????????????????{ ???????????????????????????????????????addcedge(belong[u],belong[v]); ???????????????????????????????????????addcedge(belong[v],belong[u]); ???????????????????????????????} ???????????????????????} ???????????????} ???????????????ans = cnt - 1; ???????????????lca_init(); ???????????????printf("Case %d:\n",++TC); ???????????????scanf("%d",&q); ???????????????while (q--) ???????????????{ ???????????????????????scanf("%d%d",&u,&v); ???????????????????????x = belong[u]; y = belong[v]; ???????????????????????Lca = lca(x,y); ???????????????????????x = get_root(x); ???????????????????????while (depth[x] > depth[Lca]) ???????????????????????{ ???????????????????????????????fa[x] = anc[x][0]; ???????????????????????????????ans--; ???????????????????????????????x = get_root(x); ???????????????????????} ???????????????????????y = get_root(y); ???????????????????????while (depth[y] > depth[Lca]) ???????????????????????{ ???????????????????????????????fa[y] = anc[y][0]; ???????????????????????????????ans--; ???????????????????????????????y = get_root(y); ???????????????????????} ???????????????????????printf("%d\n",ans); ???????????????} ???????????????printf("\n"); ???????} ???????????????return 0; ???}