Description
给定$N$个点和 $M$条边的无向联通图， 有$Q$ 次操作， 连接两个点的边， 问每次操作后的图中有几个桥
Solution
首先Tarjan找出边双联通分量， 每个双联通分量缩成一个点， 就构成了一棵树， 每一条树边都是桥。
执行连$u, v$ 边时， 用并查集跳到没有桥的深度最浅并且深度比$lca$深的点， 将它与父节点的并查集合并， 再接着跳。
每跳一次， 桥的数量就减少$1$。
另外感谢Iowa 神犇提醒我$cut$数组要开$M << 1$, 不是 $N << 1$, 拯救了$RE$崩溃的我呜呜
Code
?1 #include<cstdio> ?2 #include<cstring> ?3 #include<algorithm> ?4 #define rd read() ?5 using namespace std; ?6 ??7 const int N = 1e5 + 1e4; ?8 const int M = 2e5 + 1e4; ?9 ?10 int n, m, dfn[N], low[N], cnt; ?11 int head[N], tot; 12 int Head[N], Tot; 13 int col[N], col_num, father[N], ans; 14 int top[N], son[N], size[N], f[N], dep[N]; 15 int cut[M << 1]; 16 ?17 struct edge { 18 ????int nxt, to; 19 }E[M << 1], e[M << 1]; 20 ?21 int read() { 22 ????int X = 0, p = 1; char c = getchar(); 23 ????for(; c > ‘9‘ || c < ‘0‘; c = getchar()) if(c == ‘-‘) p = -1; 24 ????for(; c >= ‘0‘ && c <= ‘9‘; c = getchar()) X = X * 10 + c - ‘0‘; 25 ????return X * p; 26 } 27 ?28 void add(int u, int v) { 29 ????e[++tot].to = v; 30 ????e[tot].nxt = head[u]; 31 ????head[u] = tot; 32 } 33 ?34 void Add(int u, int v) { 35 ????E[++Tot].to = v; 36 ????E[Tot].nxt = Head[u]; 37 ????Head[u] = Tot; 38 } 39 ?40 void dfs1(int u) { 41 ????size[u] = 1; 42 ????for(int i = Head[u]; i; i = E[i].nxt) { 43 ????????int nt = E[i].to; 44 ????????if(nt == f[u]) continue; 45 ????????f[nt] = u; 46 ????????dep[nt] = dep[u] + 1; 47 ????????dfs1(nt); 48 ????????size[u] += size[nt]; 49 ????????if(size[nt] > size[son[u]]) son[u] = nt; 50 ????} 51 } 52 ?53 void dfs2(int u) { 54 ????if(!son[u]) return; 55 ????top[son[u]] = top[u]; 56 ????dfs2(son[u]); 57 ????for(int i = Head[u]; i; i = E[i].nxt) { 58 ????????int nt = E[i].to; 59 ????????if(nt == f[u] || nt == son[u]) continue; 60 ????????top[nt] = nt; 61 ????????dfs2(nt); 62 ????} 63 } 64 ?65 int LCA(int x, int y) { 66 ????for(; top[x] != top[y];) { 67 ????????if(dep[top[x]] < dep[top[y]]) swap(x, y); 68 ????????x = f[top[x]]; 69 ????} 70 ????if(dep[x] < dep[y]) swap(x, y); 71 ????return y; 72 } 73 ?74 int get(int x) { 75 ????return father[x] == x? x : father[x] = get(father[x]); 76 } 77 ?78 void merg(int x, int y) { 79 ????x = get(x); y = get(y); 80 ????father[x] = y; 81 } 82 ?83 int ch(int x) { 84 ????return ((x + 1) ^ 1) - 1; 85 } 86 ?87 void tarjan(int u, int pre) { 88 ????dfn[u] = low[u] = ++cnt; 89 ????for(int i = head[u]; i; i = e[i].nxt) { 90 ????????if(i == ch(pre)) continue; ?91 ????????int nt = e[i].to; 92 ????????????????if(!dfn[nt]) { 93 ????????????????????tarjan(nt, i); 94 ????????????????????low[u] = min(low[u], low[nt]); 95 ????????????????????if(low[nt] > dfn[u]) { 96 ????????????????????????cut[ch(i)] = cut[i] = 1; 97 ????????????????????????ans++; 98 ????????????????????} 99 ????????????????}100 ????????????????else low[u] = min(low[u], dfn[nt]);101 ????}102 }103 104 void dfs(int u) {105 ????col[u] = col_num;106 ????for(int i = head[u]; i; i = e[i].nxt) {107 ????????int nt = e[i].to;108 ????????if(col[nt] || cut[i]) continue;109 ????????dfs(nt);110 ????????//blo[col_num].push_back(nt);111 ????}112 }113 114 void work() {115 ????ans = Tot = tot = cnt = col_num = 0;116 ????memset(Head, 0, sizeof(Head));117 ????memset(head, 0, sizeof(head));118 ????memset(cut, 0, sizeof(cut));119 ????memset(dfn, 0, sizeof(dfn));120 ????memset(col, 0, sizeof(col));121 ????memset(son, 0, sizeof(son));122 ????memset(size, 0, sizeof(size));123 ????for(int i = 1; i <= m; ++i) {124 ????????int u = rd, v = rd;125 ????????add(u, v); add(v, u);126 ????}127 ????for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i, 0);128 ????for(int i = 1; i <= n; ++i) if(!col[i]) {129 ????????++col_num; dfs(i);130 ????}131 ????for(int i = 1; i <= tot; ++i) {132 ????????int x = e[i].to, y = e[ch(i)].to;133 ????????if(col[x] == col[y]) continue;134 ????????Add(col[x], col[y]);135 ????}136 ????for(int i = 1; i <= col_num; ++i) father[i] = i;137 ????dfs1(1);138 ????top[1] = 1; dfs2(1);139 ????int T = rd;140 ????for(; T; T--) {141 ????????int u = col[rd], v = col[rd], lca = LCA(u, v);142 ????????u = get(u); v = get(v);143 ????????while(dep[u] > dep[lca]) {144 ????????????merg(u, f[u]);145 ????????????u = get(u);146 ????????????ans --;147 ????????}148 ????????while(dep[v] > dep[lca]) {149 ????????????merg(v, f[v]);150 ????????????v = get(v);151 ????????????ans --;152 ????????}153 ????????printf("%d\n", ans);154 ????}155 }156 157 int main()158 {159 ????for(int i = 1; ; ++i) {160 ????????n = rd; m = rd;161 ????????if(!n && !m) return 0;162 ????????printf("Case %d:\n", i);163 ????????work();164 ????????putchar(‘\n‘);165 ????}166 }POJ3694 Network - Tarjan + 并查集
原文地址：https://www.cnblogs.com/cychester/p/9626945.html