欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

无向联通图的二分染色与存在奇环的性质分析

程序员文章站 2022-03-12 09:53:24
...

题引

无向联通图的二分染色与存在奇环的性质分析

无向联通图的二分染色与存在奇环的性质分析


题解及思路

题中给出了无向图的两种存在形状 二分染色 和 存在奇环

首先我们需要证明的是两者是互斥的。

二分图定义 :是这样一个图,其顶点可分为两集合X和Y,所有的边关联的两顶点中,恰一个属于X,另一个属于Y。同一集合的结点不相邻。

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

设一个环,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 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 {
            /**
            printf("%d\n",root);
            for(int i=1;i<=n;i++) printf("%d ",path[i]);printf("\n");
            **/
            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;
}