poj 2942 Knights of the Round Table 【双连通缩点+判奇圈】【经典】

超、凢脫俗 2022-08-13 15:50 118阅读 0赞

题目：[poj 2942 Knights of the Round Table ][poj 2942 Knights of the Round Table]

题意：n个骑士经常一起开会，其中有一些两两相互憎恨，他们不能同一桌，开会要表决一些事情，所以必须奇数个人，最少3个，求永远也参加不了会议的人的个数、

分析：这个题目两点

首先，建图求双连通缩点

建图的话，因为相互憎恨的不能再一块，所以要建补图，让能够在一起的所有的连接，这样的话，如果能存在环且环上的点是奇数个的话就可以参加会议，标记求不能参加的即可。

建好图之后用tarjan算法双连通缩点，把在一个环上的点保存起来。

第二点就是判断奇圈，我们知道二分图能够染色的肯定不是奇圈，那么我们就用二分图染色，然后求不能成功染色的点进行标记。

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <stack>
    using namespace std;
    #define MAXN 1005
    int A[MAXN][MAXN];
    int n,m;
    
    struct Edge
    {
        int u,v;
    };
    vector<int>G[MAXN],bcc[MAXN]; //bcc 存缩点之后圈中的边
    int pre[MAXN],iscut[MAXN],bccno[MAXN],dfs_clock,bcc_cnt;
    //bccno 缩点之后的点
    stack<Edge> S;
    int dfs(int u,int fa)
    {
        int lowu= pre[u]=++dfs_clock;
        int child=0;
        for(int i=0; i<G[u].size(); i++)
        {
            int v=G[u][i];
            Edge e;
            e.u=u,e.v=v;
            if(!pre[v])
            {
                S.push(e);
                child++;
                int lowv=dfs(v,u);
                lowu=min(lowu,lowv);
                if(lowv>=pre[u])
                {
                    iscut[u]=1;
                    bcc_cnt++;
                    bcc[bcc_cnt].clear();
                    for(;;)
                    {
                        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<0&&child==1)iscut[u]=0;
        return lowu;
    }
    //双连通分量
    void find_bcc(int n)
    {
        memset(pre,0,sizeof(pre));
        memset(iscut,0,sizeof(iscut));
        memset(bccno,0,sizeof(bccno));
        dfs_clock=bcc_cnt=0;
        for(int i=0; i<n; i++)
            if(!pre[i])dfs(i,-1);
    }
    //判断二分图
    int odd[MAXN],color[MAXN];
    bool bipartite(int u,int b)
    {
        for(int i=0; i<G[u].size(); i++)
        {
            int v=G[u][i];
            if(bccno[v]!=b)continue;
            if(color[v]==color[u])
                return false;
            if(!color[v])
            {
                color[v]=3-color[u];
                if(!bipartite(v,b))return false;
            }
        }
        return true;
    }
    int solve(int n)
    {
        int ans = 0;
        memset(odd,0,sizeof(odd));
        for(int i=1;i<=bcc_cnt;i++)
        {
            memset(color,0,sizeof(color));
            for(int j=0;j<bcc[i].size();j++)
            {
                int to = bcc[i][j];
                bccno[to] = i;
            }
            int u = bcc[i][0];
            color[u] = 1;
             if(!bipartite(u,i))
                for(int j=0;j<bcc[i].size();j++)
                    odd[bcc[i][j]]=1;
        }
        for(int j=0;j<n;j++)
            if(odd[j]==0)
                ans++;
        return ans;
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        while(scanf("%d%d",&n,&m)==2)
        {
            if(n==0&&m==0)
                break;
            for(int i=0; i<n; i++)
                G[i].clear();
            int a,b;
            memset(A,0,sizeof(A));
            for(int i=0; i<m; i++)
            {
                scanf("%d%d",&a,&b);
                a--,b--;
                A[b][a]=A[a][b]=1;
            }
            for(int i=0; i<n; i++)
                for(int j=i+1; j<n; j++)
                {
                    if(A[i][j])
                        continue;
                    G[i].push_back(j),G[j].push_back(i);
                }
            find_bcc(n);
            int ans = solve(n);
            printf("%d\n",ans);
        }
        return 0;
    }

[poj 2942 Knights of the Round Table]: http://poj.org/problem?id=2942