图论：双连通分支-点

POJ2942：利用Tarjan求无向图的点双连通分支

首先科普一下点双连通分支的求法：

貌似看起来繁琐而复杂。。

然而复杂的确实这道例题，暂时没有找到特别裸的。。

题干大意是这样的，开会，然后给出了一张图，边所连接的两个点互相憎恶，开会的时候只能奇数个人一起圆桌开，问T几个人会世界和平

做法的话，首先求原图的补图，然后求出补图的点双连通分量，对于每一个连通分量判断是否是二分图，如果不是二分图那么满足条件，如果是那就要T人了

这里的重点不是二分图判定，而是求点双连通分量的部分，二分图判定是在点双连通分量的基础上完成的

int n,m,cnt,deep,cnt1,ans,top,sum;
bool vis[maxn],vis1[maxn],vis2[maxn];
int g[maxn],dfn[maxn],low[maxn],tmp1[maxn],col[maxn],co[maxn],st[maxn];
int G[maxn][maxn];

图G是原图，邻接矩阵存储，既可以避免重边又可以方便建补图

然后cnt是边的数量，cnt1是临时存放的双连通分量中的点数，tmp1用来临时存放双连通分量，vis1用来判断点是否在双连通分量中

co是二分图染色数组，vis2是统计删点的

bool dfs(int u,int color)
{
    //cout<<"###"<<u<<" "<<color<<endl; 
    co[u]=color;
    for(int tmp=g[u];tmp;tmp=e[tmp].next)  //遍历子图 
    {
        int v=e[tmp].t;
        if(vis1[v]==0) continue;  //判定该点是否属于当前连通分量
        if(co[v]!=-1)
        {
            if(co[v]==color) return false;
            continue;
        }
        if(!dfs(v,!color)) return false;
    }
    return true;
}

bool dfs(int u,int color)
{
    //cout<<"###"<<u<<" "<<color<<endl; 
    co[u]=color;
    for(int tmp=g[u];tmp;tmp=e[tmp].next)  //遍历子图 
    {
        int v=e[tmp].t;
        if(vis1[v]==0) continue;  //判定该点是否属于当前连通分量
        if(co[v]!=-1)
        {
            if(co[v]==color) return false;
            continue;
        }
        if(!dfs(v,!color)) return false;
    }
    return true;
}

二分图DFS染色，代码风格不令人舒适

void tarjan(int u,int fa)
{
    //cout<<"###"<<u<<" "<<fa<<endl;
    low[u]=dfn[u]=++deep;
    vis[u]=1;
    st[++top]=u;
    for(int tmp=g[u];tmp;tmp=e[tmp].next)
    {
        int v=e[tmp].t;
        if(v==fa) continue;
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                sum++;
                int vn;
                cnt1=0;
                memset(vis1,0,sizeof(vis1));  //用于判断点是否在当前连通分量里 
                do
                {
                    vn=st[top--];
                    col[vn]=sum;
                    vis1[vn]=1;
                    tmp1[cnt1++]=vn;  //临时存点双连通分量 
                    vis[vn]=0;
                }while(vn!=v);
                vis1[u]=1;
                memset(co,-1,sizeof(co));
                if(!dfs(u,0))  //对点双连通分量进行二分图判定 
                {
                    vis2[u]=1;  //是二分图，参与记录结果 
                    while(cnt1--) vis2[tmp1[cnt1]]=1;
                }
                //top--;
            }
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
}

Tarjan求点双连通分量+做文章，标记好了vis1之后，在处理的时候扫补图，然后特判一下，连通子图就出来了

下面给出完整的实现：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int maxn=1005;
  6 const int maxm=1000005;
  7 int n,m,cnt,deep,cnt1,ans,top,sum;
  8 bool vis[maxn],vis1[maxn],vis2[maxn];
  9 int g[maxn],dfn[maxn],low[maxn],tmp1[maxn],col[maxn],co[maxn],st[maxn];
 10 int G[maxn][maxn];
 11 struct Edge{int t,next;}e[maxm];
 12 void addedge(int u,int v)
 13 {
 14     e[++cnt].t=v;e[cnt].next=g[u];
 15     g[u]=cnt;
 16 }
 17 bool dfs(int u,int color)
 18 {
 19     //cout<<"###"<<u<<" "<<color<<endl; 
 20     co[u]=color;
 21     for(int tmp=g[u];tmp;tmp=e[tmp].next)  //遍历子图 
 22     {
 23         int v=e[tmp].t;
 24         if(vis1[v]==0) continue;  //判定该点是否属于当前连通分量
 25         if(co[v]!=-1)
 26         {
 27             if(co[v]==color) return false;
 28             continue;
 29         }
 30         if(!dfs(v,!color)) return false;
 31     }
 32     return true;
 33 } 
 34 void tarjan(int u,int fa)
 35 {
 36     //cout<<"###"<<u<<" "<<fa<<endl;
 37     low[u]=dfn[u]=++deep;
 38     vis[u]=1;
 39     st[++top]=u;
 40     for(int tmp=g[u];tmp;tmp=e[tmp].next)
 41     {
 42         int v=e[tmp].t;
 43         if(v==fa) continue;
 44         if(!dfn[v])
 45         {
 46             tarjan(v,u);
 47             low[u]=min(low[u],low[v]);
 48             if(low[v]>=dfn[u])
 49             {
 50                 sum++;
 51                 int vn;
 52                 cnt1=0;
 53                 memset(vis1,0,sizeof(vis1));  //用于判断点是否在当前连通分量里 
 54                 do
 55                 {
 56                     vn=st[top--];
 57                     col[vn]=sum;
 58                     vis1[vn]=1;
 59                     tmp1[cnt1++]=vn;  //临时存点双连通分量 
 60                     vis[vn]=0;
 61                 }while(vn!=v);
 62                 vis1[u]=1;
 63                 memset(co,-1,sizeof(co));
 64                 if(!dfs(u,0))  //对点双连通分量进行二分图判定 
 65                 {
 66                     vis2[u]=1;  //是二分图，参与记录结果 
 67                     while(cnt1--) vis2[tmp1[cnt1]]=1;
 68                 }
 69                 //top--;
 70             }
 71         }
 72         else if(vis[v]) low[u]=min(low[u],dfn[v]);
 73     }
 74 }
 75 void init()
 76 {
 77     cnt=deep=cnt1=top=sum=0;
 78     memset(vis,0,sizeof(vis));
 79     memset(vis1,0,sizeof(vis1));
 80     memset(vis2,0,sizeof(vis2));
 81     memset(g,0,sizeof(g));
 82     memset(dfn,0,sizeof(dfn));
 83     memset(low,0,sizeof(low));
 84     memset(tmp1,0,sizeof(tmp1));
 85     memset(col,0,sizeof(col));
 86     memset(co,0,sizeof(co));
 87     memset(st,0,sizeof(st));
 88     memset(G,0,sizeof(G));
 89     memset(e,0,sizeof(e));
 90 }
 91 int main()
 92 {
 93     int u,v;
 94     while(scanf("%d%d",&n,&m)==2)
 95     {
 96         init();
 97         if(n==0&&m==0) break;
 98         while(m--)
 99         {
100             scanf("%d%d",&u,&v);
101             G[u][v]=G[v][u]=1;
102         }
103         for(int i=1;i<=n;i++)
104             for(int j=1;j<=n;j++)
105                 if(i!=j&&G[i][j]==0) addedge(i,j);
106         for(int i=1;i<=n;i++)
107             if(!dfn[i]) tarjan(i,-1);
108         ans=n;
109         for(int i=1;i<=n;i++)
110             if(vis2[i]) ans--;
111         printf("%d
",ans);
112     }
113     return 0;
114 }

讲道理这个题，综合性强，而且挺难的