POJ 3694 双连通缩点+LCA+并查集

题意：

给定n个点m条边的无向图

Q个询问：

问加上这条边后图中还有多少桥。

注意询问不是独立的（加了边在后面都有效）

思路：

先缩点得到缩点树，加上一条边后[u, LCA(u,v), v] 成环，则删掉这里的点，并把集合向上合并

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #define inf 107374182 #define ll int using namespace std; #define N 100100 //N为点 #define M 200100 struct Edge{ int from, to, nex; bool cut; }edge[M*2]; int head[N], edgenum; void addedge(int u, int v){ Edge E={u,v,head[u],false}; edge[ edgenum ] = E; head[u] = edgenum++; } int n, m; int dfn[N], low[N], tarjan_time, tar, Stack[N*5], top; int Belong[N]; bool iscut[N]; void tarjan(int u, int fa){ dfn[u] = low[u] = ++tarjan_time; Stack[++top] = u; int child = 0, flag = 1; for(int i = head[u]; ~i; i = edge[i].nex) { int v = edge[i].to; if(flag && v==fa){flag = 0; continue;} if(!dfn[v]) { child++; tarjan(v, u); low[u] = min(low[u], low[v]); if(low[v] >= dfn[u]) { iscut[u] = true; if(low[v]>dfn[u]) edge[i].cut = edge[i^1].cut = true; } } else low[u] = min(low[u], dfn[v]); } if(child == 1 && fa<0)iscut[u] = false; if(low[u] == dfn[u]) { tar++; do { Belong[ Stack[top] ] = tar; }while(Stack[top--] != u); } } void init(){ memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(iscut, 0, sizeof(iscut)); memset(Belong, -1, sizeof(Belong)); tarjan_time = 0; top = 0; tar = 0; tarjan(1,1); } vector
           
            G[N]; const int MAXN = 101000; int rmq[2*MAXN];//rmq数组，就是欧拉序列对应的深度序列 vector
            
             son[N]; int Father[N]; struct ST { int mm[2*MAXN]; int dp[2*MAXN][20];//最小值对应的下标 void init(int n) { mm[0] = -1; for(int i = 1;i <= n;i++) { mm[i] = ((i&(i-1)) == 0) mm[i-1]+1:mm[i-1]; dp[i][0] = i; } for(int j = 1; j <= mm[n];j++) for(int i = 1; i + (1<
             
               b)swap(a,b); int k = mm[b-a+1]; return rmq[dp[a][k]] <= rmq[dp[b-(1<