题目链接:点击打开链接
训练指南P316
//割顶的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; int n; stack<Edge> S; vector<int> G[maxn],bcc[maxn]; int map[maxn][maxn]; int color[maxn],ok[maxn]; bool fun(int x,int u) //判断该双连通分量是否为2分图 { for(int i=0;i<G[u].size();i++) { int v=G[u][i]; if(bccno[v]!=x) continue; if(color[v]==color[u]) return false; if(!color[v]) { color[v]=3-color[u]; if(!fun(x,v)) return false; } } return true; } 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; } memset(color,0,(n+10)*sizeof(color[0])); color[bcc[bcc_cnt][0]]=1; if(!fun(bcc_cnt,bcc[bcc_cnt][0])) { for(int j=0;j<bcc[bcc_cnt].size();j++) { ok[bcc[bcc_cnt][j]]=1; } } } } 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() { 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); } } int main() { int m; int k1,k2; while(scanf("%d%d",&n,&m),n||m) { memset(map,0,(n+10)*sizeof(map[0])); memset(ok,0,(n+10)*sizeof(ok[0])); while(m--) { scanf("%d%d",&k1,&k2); map[k1][k2]=1; map[k2][k1]=1; } for(k1=1;k1<=n;k1++) G[k1].clear(); for(k1=1;k1<=n;k1++) for(k2=k1+1;k2<=n;k2++) { if(map[k1][k2]==0) { G[k1].push_back(k2); G[k2].push_back(k1); } } find_bcc(); int cnt=0; for(int i=1;i<=n;i++) { if(!ok[i]) cnt++; } printf("%d\n",cnt); } return 0; }