首先弄明白什么是点双连通分量.无向图中如果删掉一个点之后连通块数目变多,这个点叫做”割点”,删掉一条边后连通块增加则这条边为"桥".无向图dfs得到一棵搜索树,不在树上的边都认为是回向边(或者说反向边). 不存在割点的极大连通子图叫做无向图的双连通分量。由此定义,图中的桥和两端的两个点也组成了一个点双连通分量. 关键是那个dfs函数.dfn[x]表示x在dfs中被发现的时间.low[x]表示x沿着树边往下走再往上走一条反向边能够到达的点中dfn[]最小是多少 感觉我这个bcc板子比蓝书的短多了(雾) poj2942 Knights of the Round Table 关于这个题怎么做,可以看蓝书.
#include<cstdio> #include<cstring> #include<vector> using namespace std; #define pb(x) push_back(x) typedef vector<int>::iterator pt; const int maxn=1005; int n,m; vector<int> bcc[maxn];int bccN; vector<int> to[maxn]; int E[maxn][maxn],eflag=0; int dfn[maxn],low[maxn],prt[maxn],T; int stk[maxn],top; void dfs(int x){//这个函数是关键 low[x]=dfn[x]=++T; for(pt i=to[x].begin();i!=to[x].end();++i){ if(*i==prt[x])continue;//恰好沿着树边往回走？不可以的 if(dfn[*i]==0){ prt[*i]=x; stk[++top]=*i;//一个点对应一条树边,代表x到*i所连的树边 dfs(*i);//递归搜索 if(low[*i]>=dfn[x]){ bcc[++bccN].clear(); do{ bcc[bccN].pb(stk[top]); }while(stk[top--]!=*i); bcc[bccN].pb(x);//注意点x还要单独加到这个BCC中 } if(low[*i]<low[x])low[x]=low[*i];//更新low[x] } if(dfn[*i]<low[x])low[x]=dfn[*i];//更新low[x] } } int good[maxn],gflag; int ufs[maxn],col[maxn]; int find(int x){ if(x==ufs[x])return x; int rt=find(ufs[x]); col[x]^=col[ufs[x]]; return ufs[x]=rt; } int bccbel[maxn],belT=0; bool link(int x,int y){ int rx=find(x),ry=find(y); if(rx!=ry){ ufs[rx]=ry; col[rx]=col[x]^col[y]^1; return false; }else{ return col[x]==col[y]; } } bool check(int x){ ++belT; for(pt i=bcc[x].begin();i!=bcc[x].end();++i){ ufs[*i]=*i;col[*i]=0;bccbel[*i]=belT; } for(pt i=bcc[x].begin();i!=bcc[x].end();++i){ for(pt j=to[*i].begin();j!=to[*i].end();++j){ if(bccbel[*j]==belT){ if(link(*i,*j))return true; } } } return false; } int main(){ while(scanf("%d%d",&n,&m),n!=0){ for(int i=1;i<=n;++i)to[i].clear(); ++eflag; for(int i=1,a,b;i<=m;++i){ scanf("%d%d",&a,&b); E[a][b]=E[b][a]=eflag; } for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j&&E[i][j]!=eflag)to[i].pb(j); memset(dfn,0,sizeof(dfn)); memset(prt,0,sizeof(prt)); memset(low,0,sizeof(low)); top=0;T=0;bccN=0; for(int i=1;i<=n;++i){ if(dfn[i]==0)dfs(i); } ++gflag; for(int i=1;i<=bccN;++i){ if(check(i)){ for(pt j=bcc[i].begin();j!=bcc[i].end();++j){ good[*j]=gflag; } } } int ans=0; for(int i=1;i<=n;++i){ if(good[i]!=gflag)++ans; } printf("%d\n",ans); } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/9239953.html
