【题意】：
有N个结点M条边的图，有Q次操作，每次操作在点x, y之间加一条边，加完E(x, y)后还有几个桥（割边），每次操作会累积，影响下一次操作。
poj2106。【思路】：
先用Tarjan求出一开始总的桥的数量，然后求边双联通分量并记录每个结点v所属的连通分量号c[v]，之后进行缩点，将每个双联通分量作为都缩成一个新点，如果新点之间可以连边就连边
(能不能连边取决于原图，我就不多bb辽，XD)，形成新图。
对于每次询问x, y，判断c[x]!=c[y]，然后从c[x]和c[y]分别向上寻找父结点，找到LCA，对c[x]寻找时经过的边数+对c[y]寻找时经过的边数==应该减去的桥数。
poj1208、考虑到每次操作的累加性，已经在之前操作中经过的边已经不是桥，不能在后续操作中再进行统计，所以使用并查集，每当c[x]，c[y]找到lca时，就将pre[c[x]] = pre[c[y]] = lca。
求LCA时涉及几乎涉及到每条边，就不使用倍增LCA（主要是我不会？？），而是用定义的方法。
下面上代码，第一个代码是求了桥，然后再进行求强联通分量，再加边。 第二个是先求强联通分量(当然是有限制的，不然因为整个图就是联通的，肯定就一个SCC了)，再加边。
poj2352，个人倾向于第二种袄，而且速度快
#include <iostream> #include <cstring> #include <cstdio> #include <map> #include <map> using namespace std;const int maxn = 1e6 + 5; const int maxm = maxn<<1; struct edge{int to, next; } ed[maxm<<1]; int n, m, q; int head[maxn], tot; int dfn[maxn], low[maxn], num, ans, c[maxn], dcc; int hc[maxn], vc[maxm<<1], nc[maxm<<1], tc; int pre[maxn], fa[maxn], dep[maxn], pass; bool brige[maxn], vis[maxn]; inline void init(){memset( head, -1, sizeof(head) );memset( dfn, 0, sizeof(dfn) );memset( brige, 0, sizeof(brige) );memset( c, 0, sizeof(c) );memset( vis, 0, sizeof(vis) );tot = 1; }inline void add( int u, int v ){ed[++tot].to = v; ed[tot].next = head[u]; head[u] = tot;ed[++tot].to = u; ed[tot].next = head[v]; head[v] = tot; }inline int min( int a, int b ){return a<b ? a:b; }inline void tarjan( int x, int in_edge ){dfn[x] = low[x] = ++num;for( int i=head[x]; i!=-1; i=ed[i].next ){int y = ed[i].to;if(!dfn[y]){tarjan(y, i);low[x] = min(low[x], low[y]);if( dfn[x]<low[y] ){brige[i] = brige[i^1] = 1; ans ++;}}else if( i!=(in_edge^1) ) low[x] = min(low[x], dfn[y]);} }inline void add_dcc( int u, int v ){vc[++tc] = v;nc[tc] = hc[u];hc[u] = tc; }inline void dfs_dcc( int x ){c[x] = dcc;for( int i=head[x]; i!=-1; i=ed[i].next ){int y = ed[i].to;if( brige[i] || c[y] ) continue;dfs_dcc(y);} }inline int find( int x ){return pre[x]==x ? x:pre[x] = find(pre[x]); }inline void dfs_lca( int x ){ //结点分层pre[x] = x;for( int i=hc[x]; i!=-1; i=nc[i] ){int y = vc[i];if( y!=fa[x] ){fa[y] = x;dep[y] = dep[x] + 1;dfs_lca(y);}} }inline void LCA( int x, int y ){pass = 0;x = find(x); y = find(y); //直接将x,y向上寻找的路径中已经计算过得边略过while( dep[y]!=dep[x] ){if( dep[y]>dep[x] ){int f = find(fa[y]); //当pre[y] == y时f是y的父亲，当pre[y]在y上方时，f就是相当于爷爷或者更高的祖辈y = pre[y] = f; //不能写成pre[y] = y = f这样y先被赋值，pre[y]则改变的是赋值后的y即pre[f]被改变pass ++; }else{int f = find(fa[x]);x = pre[x] = f;pass++;}}while( find(x)!=find(y) ){pre[x] = find(fa[x]);pre[y] = find(fa[y]);x = pre[x]; y = pre[y];pass += 2;} }int main(){// freopen("in.txt", "r", stdin);int kase = 1;while( ~scanf("%d%d", &n, &m), n||m ){init();for( int i=0; i<m; i++ ){int u, v;scanf("%d%d", &u, &v);add(u, v);}ans = dcc = num = 0;tarjan(1, 0);for( int i=1; i<=n; i++ ) if( !c[i] ) ++dcc, dfs_dcc(i);memset( hc, -1, sizeof(hc) );tc = 1;//不要使用map作为标记，遍历边进行新图的加边操作，map会TLEfor( int u=1; u<=n; u++ ){for( int i=head[u]; i!=-1; i=ed[i].next ){int v = ed[i].to;if( c[u]==c[v] ) continue;add_dcc(c[u], c[v]);}}ans = tc>>1;dep[1] = 1;fa[1] = 0;dfs_lca(1); scanf("%d", &q);printf("Case %d:\n", kase++);while( q-- ){int x, y;scanf("%d%d", &x, &y);if( c[x]!=c[y] ){LCA(c[x], c[y]);ans -= pass;}printf("%d\n", ans);}puts("");}return 0; }
#include <iostream> #include <cstring> #include <cstdio> #include <map> #include <map> using namespace std;const int maxn = 1e6 + 5; const int maxm = maxn<<1; struct edge{int to, next; } ed[maxm<<1]; int n, m, q; int head[maxn], tot, st[maxn]; int dfn[maxn], low[maxn], num, ans, c[maxn], dcc; int hc[maxn], vc[maxm<<1], nc[maxm<<1], tc; int pre[maxn], fa[maxn], dep[maxn], pass; bool ins[maxn], vis[maxn]; inline void init(){memset( head, -1, sizeof(head) );memset( dfn, 0, sizeof(dfn) );memset( c, 0, sizeof(c) );memset( vis, 0, sizeof(vis) );tot = 1; }inline void add( int u, int v ){ed[++tot].to = v; ed[tot].next = head[u]; head[u] = tot;ed[++tot].to = u; ed[tot].next = head[v]; head[v] = tot; }inline int min( int a, int b ){return a<b ? a:b; }inline void tarjan( int x, int in_edge ){dfn[x] = low[x] = ++num;ins[x] = 1;st[++st[0]] = x;for( int i=head[x]; i!=-1; i=ed[i].next ){int y = ed[i].to;if( i==(in_edge^1) ) continue;if(!dfn[y]){tarjan(y, i);low[x] = min(low[x], low[y]);}else if( ins[y] ) low[x] = min(low[x], dfn[y]);}if( dfn[x]==low[x] ){dcc ++;int p;do{p = st[st[0]--];c[p] = dcc;ins[p] = 0;}while( p!=x );} }inline void add_dcc( int u, int v ){vc[++tc] = v;nc[tc] = hc[u];hc[u] = tc; }inline int find( int x ){return pre[x]==x ? x:pre[x] = find(pre[x]); }inline void dfs_lca( int x ){pre[x] = x;for( int i=hc[x]; i!=-1; i=nc[i] ){int y = vc[i];if( y!=fa[x] ){fa[y] = x;dep[y] = dep[x] + 1;dfs_lca(y);}} }inline void LCA( int x, int y ){pass = 0;x = find(x); y = find(y);while( dep[y]!=dep[x] ){if( dep[y]>dep[x] ){int f = find(fa[y]); //当pre[y] == y时f是y的父亲，当pre[y]在y上方时，f就是相当于爷爷或者更高的祖辈y = pre[y] = f; //不能写成pre[y] = y = f这样y先被赋值，pre[y]则改变的是赋值后的y即pre[f]被改变pass ++; }else{int f = find(fa[x]);x = pre[x] = f;pass++;}}while( find(x)!=find(y) ){pre[x] = find(fa[x]);pre[y] = find(fa[y]);x = pre[x]; y = pre[y];pass += 2;} }int main(){// freopen("in.txt", "r", stdin);int kase = 1;while( ~scanf("%d%d", &n, &m), n||m ){init();for( int i=0; i<m; i++ ){int u, v;scanf("%d%d", &u, &v);add(u, v);}ans = dcc = num = 0;for( int i=1; i<=n; i++ ) if(!dfn[i]) tarjan(1, 0);memset( hc, -1, sizeof(hc) );tc = 1;for( int u=1; u<=n; u++ ){for( int i=head[u]; ~i; i=ed[i].next ){int v = ed[i].to;if( c[u]==c[v] ) continue;add_dcc(c[u], c[v]);}}ans = tc>>1;dep[1] = 1;fa[1] = 0;dfs_lca(1);scanf("%d", &q);printf("Case %d:\n", kase++);while( q-- ){int x, y;scanf("%d%d", &x, &y);if( c[x]!=c[y] ){LCA(c[x], c[y]);ans -= pass;}printf("%d\n", ans);}puts("");}return 0; }
