UVA-1364.Knights of the Round Table 无向图BCC

题目链接：https://vjudge.net/problem/UVA-1364

题意：有n个人参加会议，互相憎恨的人不能坐在相邻的位置，并且每个会议参加的人数必须是奇数，求有多少个人不能参加任何一个会议。

思路：如果两个人可以坐在一起，则在他们之间建立一条无向边。求不在任何一个简单奇圈上面的点的个数。简单圈上面的点必然属于同一个点双联通分量，因此首先需要找出所有的点双联通分量、因为二分图是没有奇圈的，所以需要求那些不是二分图的点双联通分量。虽然这些点双联通分量一定含有奇圈，那么是否是所有的点都在奇圈上面呢。v属于点双联通分量B，但是不在属于B的奇圈C上面。根据点双联通的性质，v一定可以到达C中的一个结点u1，v也一定可以到达C中的入一个结点u2，在C中u1到u2的两条路的长度一奇一偶，总能构建出一个奇圈。

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<map>

#include<stack>

#include<vector>

using namespace std;

const int MAXN=1e3+,INF=0x3f3f3f3f,MOD=1e9+;

int n,m;

int vis[MAXN][MAXN];

vector<int>G[MAXN];

int dfs_color=;    ///dfs时间戳

int pre[MAXN],post[MAXN];

int bcc_cnt=;   ///联通分量

int low[MAXN];  ///u及其后代所能连回的最早祖先的pre值

int iscut[MAXN];    ///割点

vector<pair<int,int> >birdge;   ///桥

struct edge

{

    int u,v;

};

stack<edge>S;

int bccno[MAXN];    ///点所在的双联通分量

vector<int>bcc[MAXN];   ///双联通分量

int dfs(int u,int fa)

{

    int lowu=pre[u]=++dfs_color;

    int child=;

    for(int i=; i<G[u].size(); i++)

    {

        int v=G[u][i];

        edge e=(edge)

        {

            u,v

        };

        if(!pre[v])

        {

            S.push(e);

            child++;

            int lowv=dfs(v,u);

            lowu=min(lowu,lowv);

            if(lowv>=pre[u])

            {

                iscut[u]=true;

                if(lowv>pre[u]) birdge.push_back(make_pair(u,v));

                bcc_cnt++;

                bcc[bcc_cnt].clear();

                while(!S.empty())

                {

                    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<&&child==) iscut[u]=;

    low[u]=lowu;

    return low[u];

}

void find_bcc()

{

    bcc_cnt=;

    dfs_color=;

    memset(pre,,sizeof(pre));

    memset(iscut,,sizeof(iscut));

    memset(bccno,,sizeof(bccno));

    for(int i=; i<=n; i++)

        if(!pre[i]) dfs(i,-);

}

void init(int n,int m)

{

    memset(vis,,sizeof(vis));

    for(int i=; i<=n; i++) G[i].clear();

    birdge.clear();

    while(m--)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        vis[u][v]=vis[v][u]=;

    }

    for(int i=; i<=n; i++)

    {

        for(int j=; j<i; j++)

        {

            if(vis[i][j]) continue;

            G[i].push_back(j);

            G[j].push_back(i);

        }

    }

}

int color[MAXN];

int odd[MAXN];

bool bipartite(int u,int d)

{

    for (int i = ; i < G[u].size(); i++)

    {

        int v=G[u][i];

        if (bccno[v]!=d) continue;

        if (color[v]==color[u]) return false;

        if (!color[v])

        {

            color[v]=-color[u];

            if (!bipartite(v,d)) return false;

        }

    }

    return true;

}

int solve()

{

    memset(odd,,sizeof(odd));

    for(int i=; i<=bcc_cnt; i++)

    {

        for(int j=;j<bcc[i].size();j++) bccno[bcc[i][j]]=i;

        memset(color,,sizeof(color));

        color[bcc[i][]]=;

        if(!bipartite(bcc[i][],i))

        {

            for (int j=; j<bcc[i].size(); j++)

                odd[bcc[i][j]]=;

        }

    }

    int ans=;

    for(int i=; i<=n; i++)

        if(!odd[i]) ans++;

    return ans;

}

int main()

{

    while(scanf("%d%d",&n,&m))

    {

        if(n==&&m==) break;

        init(n,m);

        find_bcc();

        cout<<solve()<<endl;

    }

    return ;

}

无向图BCC+二部图