求桥，缩点，LCA，还有重边，之后还要加Q条边，每次加完后询问一次桥的个数。。。个人感觉算是比较麻烦的题了。。。
给出N个点，M条边，保证所有点连通，数据中有重边，之后加入Q条边，每次加完后，输出一个整数代表图中剩余的桥的数量。
首先找出所有的桥，将桥删除，然后将双连通分量进行缩点，用桥将这些点连接起来，然后用LCA处理。
对于每条新加入的边，首先判断其两端点被缩进了哪个点，设其分别被缩进了 u, v。
则因这条边而消除的桥，必为 [ LCA（u,v） , u ] 和 [ LCA(u,v) , v ]两条路上的桥。
#include#include #include #include #include #include #include #define LL long long #define PI (acos(-1.0)) #define EPS (1e-10) using namespace std; const int MAXN = 100010; struct N { int v,next; }Edge[MAXN*4],Lca_Edge[MAXN*4]; struct E { int u,v; }Bridge[MAXN*2]; int Top_Edge,Top_Bridge,Lca_Top_Edge,Lca_Time; int head[MAXN]; int Lca_Head[MAXN]; int mv[MAXN]; int depth[MAXN]; int Lca_Depth[MAXN]; int Lca_Vis[MAXN]; int Point[MAXN*2]; int st[MAXN*8]; int father[MAXN]; int root[MAXN]; bool Cut[MAXN]; void link(int u,int v) { Edge[++Top_Edge].v = v; Edge[Top_Edge].next = head[u]; head[u] = Top_Edge; } void Lca_Link(int u,int v) { Lca_Edge[++Lca_Top_Edge].v = v; Lca_Edge[Lca_Top_Edge].next = Lca_Head[u]; Lca_Head[u] = Lca_Top_Edge; } int Find(int x) { while(x != father[x]) x = father[x]; return x; } void Merge(int u,int v) { int fu = Find(u); int fv = Find(v); if(fu != fv) { father[fu] = fv; } } int Dfs(int s,int f,int h) { mv[s] = 1;//表示灰色，即已开始DFS且正在等待回溯 depth[s] = h; int p,Temp_Depth,Min_Depth = MAXN; bool Cover = false; for(p = head[s];p != -1;p = Edge[p].next) { if(Edge[p].v != f || Cover) { if(mv[Edge[p].v] == 0) { Temp_Depth = Dfs(Edge[p].v,s,h+1); if(Temp_Depth < Min_Depth) Min_Depth = Temp_Depth; } else if(mv[Edge[p].v] == 1) { if(depth[Edge[p].v] < Min_Depth) Min_Depth = depth[Edge[p].v]; } } else Cover = true; } if(f != -1 && Min_Depth >= depth[s]) { Bridge[Top_Bridge].u = f; Bridge[Top_Bridge].v = s; Top_Bridge++; } else if(f != -1) { Merge(f,s); } return Min_Depth; } void Lca_Dfs(int s,int h) { Lca_Depth[s] = h; Point[Lca_Time] = s; Lca_Vis[s] = Lca_Time++; for(int p = Lca_Head[s]; p != -1; p = Lca_Edge[p].next) { if(Lca_Vis[Lca_Edge[p].v] == -1) { root[Lca_Edge[p].v] = s; Cut[Lca_Edge[p].v] = false; Lca_Dfs(Lca_Edge[p].v,h+1); Point[Lca_Time++] = s; } } } void Init_St(int site,int l,int r) { if(l == r) { st[site] = Lca_Depth[Point[l]]; return ; } int mid = (l+r)>>1; Init_St(site<<1,l,mid); Init_St(site<<1|1,mid+1,r); if(st[site<<1] < st[site<<1|1]) st[site] = st[site<<1]; else st[site] = st[site<<1|1]; } int Query_St(int site,int L,int R,int l,int r) { if(l == L && R == r) { return st[site]; } int mid = (L+R)>>1; if(mid < l) { return Query_St(site<<1|1,mid+1,R,l,r); } else if(r <= mid) { return Query_St(site<<1,L,mid,l,r); } int h1 = Query_St(site<<1,L,mid,l,mid); int h2 = Query_St(site<<1|1,mid+1,R,mid+1,r); return (h1 < h2 h1 : h2); } int Query(int u,int v) { int h; if(Lca_Vis[u] < Lca_Vis[v]) h = Query_St(1,0,Lca_Time-1,Lca_Vis[u],Lca_Vis[v]); else h = Query_St(1,0,Lca_Time-1,Lca_Vis[v],Lca_Vis[u]); int i,f,ans = 0; //cout<