POJ 2942(点双连通分量+无向图判奇环)

题目链接：传送门

题意：

来自kuangbin模板

POJ 2942 Knights of the Round Table

亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突， 并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求： 1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置； 2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。

注意：1、所给出的憎恨关系一定是双向的，不存在单向憎恨关系。 2、由于是圆桌会议，则每个出席的骑士身边必定刚好有2个骑士。 即每个骑士的座位两边都必定各有一个骑士。 3、一个骑士无法开会，就是说至少有3个骑士才可能开会。

思路：

首先根据给出的互相憎恨的图中得到补图。 然后就相当于找出不能形成奇圈的点。 利用下面两个定理：

（1）如果一个点双连通分量内的某些顶点在一个奇圈中（即点双连通分量含有奇圈）， 那么这个点双连通分量的其他顶点也在某个奇圈中；

（2）如果一个点双连通分量含有奇圈，则他必定不是一个二分图。反过来也成立，这是一个充要条件。

所以本题的做法，就是对补图求点双连通分量。 然后对于求得的点双连通分量，使用染色法判断是不是二分图，不是二分图，这个双连通分量的点是可以存在的

bing神nb

代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=1e3+10;
bool hate[N][N];
vector<int> g[N];
int dfn[N],tol,low[N],S[N],top,belong[N],block;
bool ins[N];
bool have[N],canjoin[N];//have[i]表示i点是否在当前点双连通分量中
int temp[N];//temp用来储存当前点双联通分量的点,用于记录可以参加会议的骑士
int color[N];
bool dfs(int u,int sg)//二分图交叉染色法
{
    if(color[u]==sg) return true;
    if(color[u]!=-1&&color[u]!=sg) return false;
    color[u]=sg;
    for(int i=0;i<g[u].size();++i)
    {
        int v=g[u][i];
        if(have[v]){
            if(!dfs(v,sg^1)) return false;
        }
    }
    return true;
}
bool judge(int tot)//有奇圈返回true，没有奇圈(是二分图)返回false
{
    mset(color,-1);
    bool ok=dfs(temp[0],0);
    return !ok;
}
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++tol;
    S[top++]=u;
    ins[u]=true;
    for(int i=0;i<g[u].size();++i)
    {
        int v=g[u][i];
        if(v==fa) continue;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                int vn,tot=0;
                mset(have,0);
                block++;
                do{
                    vn=S[--top];
                    ins[vn]=false;
                    belong[vn]=block;
                    /*这里存储所有点双连通分量的点,用于检测奇环*/
                    have[vn]=true;
                    temp[tot++]=vn;
                }
                while(vn!=v);
                //注意u也是该点双连通分量的点,且一个割点可以在多个点双连通分量
                /*下面是处理判断该点双连通分量能否参加会议*/
                have[u]=true;
                temp[tot++]=u;
                if(judge(tot))
                {
                   while(tot--) canjoin[temp[tot]]=true;
                }
            }
        }
        else if(ins[v])
            low[u]=min(low[u],dfn[v]);
    }
}
void solve(int n)
{
    top=tol=block=0;
    mset(dfn,0);mset(belong,0);mset(ins,0);
    mset(canjoin,0);
    for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,i);
    int ans=0;
    for(int i=1;i<=n;++i)
        if(!canjoin[i]) ans++;
    printf("%d\n",ans);
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m),n)
    {
        mset(hate,0);
        for(int i=0;i<m;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            hate[u][v]=true;
            hate[v][u]=true;
        }
        for(int i=1;i<=n;++i) g[i].clear();
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
                if(!hate[i][j]&&i!=j)
                    g[i].push_back(j);
        }
        solve(n);
    }
    return 0;
}