//割顶的bccno无意义 #include<cstdio> #include<cstring> #include<stack> #include<vector> using namespace std; #define maxn 1100 struct Edge{ int u,v; }; int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt; stack<Edge> S; vector<int> G[maxn],bcc[maxn]; int dfs(int u,int fa) { int lowu=pre[u]=++dfs_clock; int child=0; for(int i=0;i<G[u].size();i++) { int v=G[u][i]; Edge e; e.u=u; e.v=v; if(!pre[v]) //没有访问过v { S.push(e); child++; int lowv=dfs(v,u); lowu=min(lowu,lowv); //用后代的low函数更新自己 if(lowv>=pre[u]) { iscut[u]=true; bcc_cnt++; bcc[bcc_cnt].clear(); //bcc从1开始编号 while(1) { Edge x=S.top(); S.pop(); if(bccno[x.u]!=bcc_cnt) { bcc[bcc_cnt].push_back(x.u); bccno[x.u]=bcc_cnt; } if(bccno[x.v]!=bcc_cnt) { bcc[bcc_cnt].push_back(x.v); bccno[x.v]=bcc_cnt; } if(x.u==u && x.v==v) break; } } } else if(pre[v]<pre[u] && v!=fa) { S.push(e); lowu=min(lowu,pre[v]); //用反向边跟新自己 } } if(fa<0 && child==1) iscut[u]=0; return lowu; } void find_bcc(int n) { memset(pre,0,(n+10)*sizeof(pre[0])); memset(iscut,0,(n+10)*sizeof(iscut[0])); memset(bccno,0,(n+10)*sizeof(bccno[0])); dfs_clock=bcc_cnt=0; for(int i=0;i<n;i++) { if(!pre[i]) dfs(i,-1); } }