牛客国庆集训派对Day3 J Graph Coloring I

骑猪看日落 2022-05-09 07:14 150阅读 0赞

## 题目：[点击打开链接][Link 1] ##

## 题意：判断一个图是否能用两种颜色染色，满足相邻点的颜色不同。 ##

## 分析：可以直接对图进行染色，如果发现当前点的颜色与已经染色的相邻点相同，则存在奇环（环山点的总数为奇数）。也可以判断是否为二分图，因为二分图与奇环互斥。 ##

## 证明：假设二分图中的环是奇数环。 ##

## 设一个环，x1，x2，x3，，，，x(2\*k-1)，k>=1且为整数。相邻两点有边连接，x1与x(2\*k-1)相连。 ##

## 由二分图定义可知：x1与x2分别在X集合和Y集合，由于x2与x3的关系可知x3在X集合，则x4在Y集合，以此类推，可得奇数点在X集合，偶数点在Y集合，那么点x(2\*k-1)则在X集合中，即与x1同为一个集合，但有之间假设的x1与x(2\*k-1)有连边，那么此时就与二分图定义不符，这二分图中的环不可能是奇数环。 ##

## 只需要DFS对无向图进行二分染色，如果不满足二分图，即我们找到了顶点v和u染色错误。vu顶点构成的这条路径一定是一个奇环。根据dfs的顺序回溯即可还原这条路径。 ##

## 代码一： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 3e5 + 10;
    int n, m;
    bool vis[N];
    vector<int> g[N];
    int a[N], ans[N], cnt;
    bool flag;
    int st;
    void DFS1(int x, int y)
    {
        vis[x] = 1;
        a[x] = y;
        for(int i = 0; i < g[x].size(); i++)
            if(!vis[g[x][i]])
                DFS1(g[x][i], (y + 1) % 2);
            else if(a[g[x][i]] == y)
                flag = 0, st = g[x][i];
    }
    void DFS2(int x)
    {
        if(flag) return;
        ans[++cnt] = x;
        vis[x] = 1;
        for(int i = 0; i < g[x].size(); i++)
            if(!vis[g[x][i]])
                DFS2(g[x][i]);
            else if(g[x][i] == st && cnt % 2 != 0)
                flag = 1;
        if(!flag) cnt--;
    }
    int main()
    {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        memset(vis, 0, sizeof(vis));
        flag = 1;
        DFS1(1, 0);
        if(flag)
        {
            printf("0\n");
            for(int i = 1; i <= n; i++)
                printf("%d ", a[i]);
            printf("\n");
        }
        else
        {
            flag = 0;
            memset(vis, 0, sizeof(vis));
            DFS2(st);
            printf("%d\n", cnt);
            for(int i = 1; i <= cnt; i++)
                printf("%d ", ans[i]);
            printf("\n");
        }
    }

## 代码二： ##

#include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    const int maxn = 3e5+10;
    vector<int> ways[maxn];
    int col[maxn],path[maxn],n,m,root;
    vector<int> ans;
    bool flag;
    inline void init() {
        memset(col,-1,sizeof(col));
        memset(path,-1,sizeof(path));
        ans.clear();
        flag = true;
        for(int i=0;i<maxn;i++) ways[i].clear();
    }
    inline void addedge(int u,int v) {
        ways[u].push_back(v);
        ways[v].push_back(u);
    }
    void dfs(int rt,int c) {
        if(!flag) return ;
        col[rt] = c;
        for(int i=0;i<ways[rt].size();i++) {
            if(!flag) return;
            if(col[ways[rt][i]] == -1) {
                path[ways[rt][i]] = rt;
                dfs(ways[rt][i],c^1);
            }
            else {
                if(col[ways[rt][i]] == c) {
                    path[ways[rt][i]] = rt;
                    flag = false;
                    root = ways[rt][i];
                    return;
                }
            }
        }
    }
    int main()
    {
        while(~scanf("%d%d",&n,&m)) {
            init();
            for(int i=0,u,v;i<m;i++) {
                scanf("%d%d",&u,&v);
                addedge(u,v);
            }
            dfs(1,0);
            if(flag) {
                printf("0\n");
                for(int i=1;i<n;i++) printf("%d ",col[i]);printf("%d\n",col[n]);
            }
            else {
                int now = path[root];
                ans.push_back(root);
                while(root != now) {
                    ans.push_back(now);
                    now = path[now];
                }
                int k = ans.size();
                printf("%d\n",k);
                for(int i=0;i<k-1;i++) printf("%d ",ans[i]);printf("%d\n",ans[k-1]);
            }
        }
        return 0;
    }

[Link 1]: https://www.nowcoder.com/acm/contest/203/J