poj2942 求v-DCC，二分图判奇环，补图

/* 给定一张无向图，求有多少点不被任何奇环包含 推论1：如果两个点属于两个不同的v-DCC,则他们不可能在同一个奇环内 推论2：某个v-DCC中有奇环，则这个v-DCC中所有点必定被属于某个奇环 只要求出补图中的所有v-DCC,判定每个v-DCC中是否存在奇环即可 如果某个v-DCC中包含奇环，则该联通块的所有点都被标记位1 最后只要求未被标记的点数量即可 */ #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define maxn 1005 int mp[maxn][maxn]; struct Edge{int to,nxt;}edge[2000005]; int head[maxn],tot,n,m; void addedge(int u,int v){ edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++; } int ind,top,low[maxn],dfn[maxn],stack[maxn],flag[maxn],color[maxn],tmp[maxn],cnt; int ok[maxn];//判断i是否在联通分量里 int dfs(int x,int col){//不能成功染色就返回0 color[x]=col; for(int i=head[x];i!=-1;i=edge[i].nxt){ int y=edge[i].to; if(ok[y]==0)continue; if(color[y]!=-1){//已经被染色过的点 if(color[y]==col) return false; continue; } if(!dfs(y,col^1)) return false; } return true; } void Tarjan(int x){ dfn[x]=low[x]=++ind; stack[++top]=x; for(int i=head[x];i!=-1;i=edge[i].nxt){ int y=edge[i].to; if(!dfn[y]){ Tarjan(y); low[x]=min(low[x],low[y]); if(dfn[x]<=low[y]){//找到一个点双联通分量 int z; cnt=0; memset(ok,0,sizeof ok); do{ z=stack[top--]; tmp[++cnt]=z; ok[z]=1; }while(z!=y); tmp[++cnt]=x; //tmp数组中存点双联通分量 //开始判定奇环 memset(color,-1,sizeof color); ok[x]=1; if(!dfs(x,0)){//如果v_DCC中有奇环 flag[x]=1; while(cnt--) flag[tmp[cnt]]=1; } } } else low[x]=min(low[x],dfn[y]); } } void init(){ tot=ind=top=0; memset(head,-1,sizeof head); memset(low,0,sizeof low); memset(dfn,0,sizeof dfn); memset(flag,0,sizeof flag); memset(mp,0,sizeof mp); } int main(){ while(cin>>n>>m,n){ init(); int u,v; while(m--){ scanf("%d%d",&u,&v); mp[u][v]=mp[v][u]=1; } //建立补图 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(mp[i][j]==0) addedge(i,j),addedge(j,i); for(int i=1;i<=n;i++) if(dfn[i]==0) Tarjan(i); int ans=n; for(int i=1;i<=n;i++) if(flag[i])ans--; cout<<ans<<endl; } }

 

转载于:https://www.cnblogs.com/zsben991126/p/10461051.html