【POJ 2942】Knights of the Round Table（点双连通分量，二分图染色）

圆桌会议必须满足：奇数个人参与，相邻的不能是敌人（敌人关系是无向边）。

求无论如何都不能参加会议的骑士个数。只需求哪些骑士是可以参加的。

我们求原图的补图：只要不是敌人的两个人就连边。

在补图的一个奇圈里（由奇数个点组成的环）每个点都是可以参加的。而一个奇圈一定在点双连通分量里，所以我们把原图的每个点双连通分量找出来，然后判断是否有奇圈。用到了几个引理：

非二分图至少有一个奇圈。

点双连通分量如果有奇圈，那么每个点都在某个奇圈里（不一定是同一个）。

于是问题转化为对每个点双连通分量，判断它是不是二分图，如果不是，那就把它里面所有点都标记为可行，最后用总数减去可行的就是答案（无论如何都不能参加会议的骑士个数）。

二分图染色就是dfs，对一个点染色后，对其相邻点染上与自己不同的颜色，如果相邻点已经染过，就判断其颜色是否和自己相同，是则说明不是二分图，否则跳过该相邻点。直到全部染完。

#include<cstdio>

#include<cstring>

const int N = ;

const int M = ;

struct Edge

{

    int to,next;

}edge[M];

int head[N],tot;

int Low[N],DFN[N],Stack[N],Belong[N];

int Index,top;

int block;//点双连通分量的个数

bool Instack[N];

bool can[N];

bool ok[N];//标记

int tmp[N];//暂时存储双连通分量中的点

int cc;//tmp的计数

int color[N];//染色

void addedge(int u,int v)

{

    edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;

}

bool dfs(int u,int col)//染色判断二分图

{

    color[u] = col;

    for(int i = head[u];~i;i = edge[i].next)

    {

        int v = edge[i].to;

        if( !ok[v] )continue;

        if(~color[v])

        {

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

            continue;

        }

        if(!dfs(v,!col))return false;

    }

    return true;

}

void Tarjan(int u,int pre)

{

    int v;

    Low[u] = DFN[u] = ++Index;

    Stack[top++] = u;

    Instack[u] = true;

    for(int i = head[u];~i;i = edge[i].next)

    {

        v = edge[i].to;

        if(v == pre)continue;

        if( !DFN[v] )

        {

            Tarjan(v,u);

            if(Low[u] > Low[v])Low[u] = Low[v];

            if( Low[v] >= DFN[u])

            {

                block++;

                int vn;

                cc = ;

                memset(ok,false,sizeof ok);

                do

                {

                    vn = Stack[--top];

                    Belong[vn] = block;

                    Instack[vn] = false;

                    ok[vn] = true;

                    tmp[cc++] = vn;

                }

                while( vn!=v );

                ok[u] = ;

                memset(color,-,sizeof(color));

                if( !dfs(u,) )

                {

                    can[u] = true;

                    while(cc--)can[tmp[cc]]=true;

                }

            }

        }

        else if(Instack[v] && Low[u] > DFN[v])

            Low[u] = DFN[v];

    }

}

void solve(int n)

{

    memset(DFN,,sizeof DFN);

    memset(Instack,false,sizeof Instack);

    Index = block = top = ;

    memset(can,false,sizeof can);

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

        if(!DFN[i])

            Tarjan(i,-);

    int ans = n;

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

        if(can[i])

            ans--;

    printf("%d\n",ans);

}

void init()

{

    tot = ;

    memset(head,-,sizeof head);

}

int g[N][N];

int main()

{

    int n,m,u,v;

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

    {

        init();

        memset(g,,sizeof g);

        while(m--)

        {

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

            g[u][v]=g[v][u]=;

        }

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

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

                if(i != j && g[i][j]==)

                    addedge(i,j);

        solve(n);

    }

    return ;

}

巴特西

【POJ 2942】Knights of the Round Table（点双连通分量，二分图染色）

最新文章

热门文章