hdoj1814 Peaceful Commission【2-set】

ゝ一纸荒年。 2022-08-08 12:45 4阅读 0赞

题目：[hdoj1814 Peaceful Commission][]

讲解：[这里][Link 1]  
这是这个题目要输出字典序最小的解，刚好第一种暴力的解法输出来的就是原题目的解，因为每次染色的时候先染字典序小的，所以肯定对。  
AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <cmath>
    #include <stack>
    #include <algorithm>
    using namespace std;
    const int N = 8200;
    bool vis[2*N];
    struct TwoSet
    {
        vector<int> G[2*N];
        int s[2*N],c;
        void init(int n)
        {
            for(int i=0;i<=2*n;i++)
                G[i].clear();
            memset(vis,false,sizeof(vis));
        }
        void add_Node(int x,int y)
        {
            G[x].push_back(y^1);
            G[y].push_back(x^1);
        }
        bool dfs(int x)
        {
            if(vis[x^1])
                return false;
            if(vis[x])
                return true;
            vis[x] = true;
            s[c++] = x;
            for(int i=0;i<G[x].size();i++)
            {
                if(!dfs(G[x][i]))
                    return false;
            }
            return true;
        }
        bool yougth(int n)
        {
            for(int i = 0;i< 2*n;i+=2)
            {
                if(!vis[i] && !vis[i+1])
                {
                    c = 0;
                    if(!dfs(i))
                    {
                        while(c>0)
                            vis[ s[--c] ] = false;
                        if(!dfs(i+1))
                            return false;
                    }
                }
            }
            return true;
        }
    };
    TwoSet solve;
    int main()
    {
    //    freopen("Input.txt","r",stdin);
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            solve.init(n);
            for(int i=0;i<m;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                x--,y--;
                solve.add_Node(x,y);
            }
             if (!solve.yougth(n)) printf("NIE\n");
                  else
                  {
                         for (int i=0;i<(n<<1);i++)
                            if (vis[i]==1) printf("%d\n",i+1);
                  }
        }
        return 0;
    }

[hdoj1814 Peaceful Commission]: http://acm.hdu.edu.cn/showproblem.php?pid=1814
[Link 1]: http://blog.csdn.net/y990041769/article/details/45787751