摘要：
主题链接：https://vjudge.net/problem/POJ-3694主题：给定一个连通图，找出桥的数量。每次查询时，都添加一条边。询问添加此边后有多少桥。想法：tarjan+并发集合查询+lca（幼稚）首先，使用tarjan收缩点（收缩环中的点），然后同时降低桥以将每个scc保存到下一个源点（boss）：此点表示scc）。使用保存的桥通过使用组合查询集创建新的图。为了便于以后的操作，可以通过查询集合来创建树
题目链接：https://vjudge.net/problem/POJ-3694
题目：给定一个连通图，求桥的个数，每次查询，加入一条边，问加入这条边后还有多少个桥。
思路：tarjan + 并查集 + lca（朴素）
先用tarjan缩点（成环缩点），并存下桥，把每个scc都存下一个源点（源点（boss）：以这个点代表这个scc）。
用存下的桥，用并查集重新建图，为了方便之后的操作，并查集建立一颗树，dfn小的在上，dfn大的在下。
并且标记x和fa[x]之间有桥，在lca过程中，如果fa[x].bridge == 1，说明这个桥仍然存在，然后fa[x].bridge = 0，防止重复计算
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 using namespace std; 6 #define pb push_back 7 8 const int N = (int)5e5+10; 9 int n,m,tot,tim,top,scc,ans;//点，边，链式前向星，时间戳，栈，连通数 10 int head[N],dfn[N],low[N],scc_no[N],s[N],boss[N]; 11 //链式前向星，dfn，low，联通块编号，栈，父节点，源点 12 struct node{ 13 int to; 14 int nxt; 15 }e[N << 1]; 16 struct _cut{ 17 int x,y; 18 }; 19 struct xx{ 20 int fa; 21 int bridge; 22 }fa[N]; 23 vector<_cut> cut;//桥 24 vector<int> poi;//lca 25 26 void init(){ 27 for(int i = 0; i <= n; ++i){ 28 head[i] = -1; 29 dfn[i] = 0; 30 } 31 cut.clear(); 32 scc = tim = tot = 0; 33 } 34 35 inline void add(int u,int v){ 36 e[tot].to = v; 37 e[tot].nxt = head[u]; 38 head[u] = tot++; 39 } 40 41 void tarjan(int now,int pre){ 42 dfn[now] = low[now] = ++tim; 43 s[top++] = now; 44 45 int to,pre_cnt = 0; 46 for(int o = head[now]; ~o; o = e[o].nxt){ 47 to = e[o].to; 48 if(to == pre && pre_cnt == 0) { pre_cnt = 1; continue; } 49 if(!dfn[to]){ 50 tarjan(to,now); 51 low[now] = min(low[now],low[to]); 52 if(dfn[now] < low[to]) cut.pb(_cut{now,to}); 53 } 54 else if(low[now] > dfn[to]) low[now] = dfn[to]; 55 } 56 57 if(dfn[now] == low[now]){ 58 int p; 59 ++scc; 60 boss[scc] = now;//记录该scc的源点 61 do{ 62 p = s[--top]; 63 scc_no[p] = scc; 64 }while(now != p); 65 } 66 } 67 //得到源点函数 68 inline int _boss(int x){ 69 return boss[scc_no[x]]; 70 } 71 //重建图 boss进行并查集 72 void rebuild(){ 73 ans = cut.size(); 74 int x,y; 75 for(int i = 0; i < ans; ++i){ 76 x = _boss(cut[i].x); 77 y = _boss(cut[i].y); 78 //dfn上小，下大的树 79 if(dfn[x] > dfn[y]) swap(x,y); 80 fa[y].fa = x; 81 fa[y].bridge = 1; 82 } 83 } 84 85 void lca(int x,int y){ 86 int fax = _boss(x); 87 int fay = _boss(y); 88 //if(dfn[fax] == dfn[y]) return; 89 90 // poi.pb(fax); poi.pb(fay); 91 while(dfn[fax] != dfn[fay]){ 92 while(dfn[fax] > dfn[fay]){ 93 if(fa[fax].bridge){ 94 --ans; 95 fa[fax].bridge = 0; 96 } 97 fax = fa[fax].fa; 98 } 99 while(dfn[fax] < dfn[fay]){ 100 if(fa[fay].bridge){ 101 --ans; 102 fa[fay].bridge = 0; 103 } 104 fay = fa[fay].fa; 105 } 106 } 107 108 } 109 110 int main(){ 111 112 int _case = 0; 113 while(~scanf("%d%d",&n,&m) && (n+m)){ 114 init(); 115 int u,v; 116 for(int i = 0; i < m; ++i){ 117 scanf("%d%d",&u,&v); 118 add(u,v); add(v,u); 119 } 120 121 tarjan(1,1); 122 rebuild(); 123 124 int q; 125 scanf("%d",&q); 126 printf("Case %d: ",++_case); 127 while(q--){ 128 scanf("%d%d",&u,&v); 129 lca(u,v); 130 printf("%d ",ans); 131 } 132 } 133 134 135 136 return 0; 137 }