Codeforces Round #360 (Div. 1), problem: (A) NP-Hard Problem（二分图判定+dfs+染色法套用）+ 【二分图简介】

Codeforces Round #360 (Div. 1), problem: (A) NP-Hard Problem

题目大意

一个无向图，使得顶点集V可以分割为两个互不相交的子集A,B，使得所有边两端分别属于两个子集A,B。

题解

其实就是二分图求解过程 采用染色法 判断给你的无向边是否能形成无向图 如果不能形成二分图就输出-1 还有需要注意的一点是题目中对于孤儿结点没有任何要求 随便在哪边都可以 或者都不放也行 代码中在dfs里面没有处理孤儿结点

dfs解法

/*
    二分图，dfs染色 
    用vector数组存每个点的相邻的点，
    先将每个点的颜色标为-1，再逐个遍历，
    每当找到一个点的颜色是-1时，dfs将其及其相邻点染色；
    如果染色时发现该点已经染色了，则须进行判断
    1,如果该点的颜色与想给它染的颜色相同，则直接返回（对于写法要注意，刚开始判断放在外面，造成了死循环） 
    2，如果该点的颜色与想染的颜色不同，则说明产生了矛盾，及该图不能成为二分图，标记并返回 
    最后打印就好 
*/

#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=1e5+10;
vector<int> vr[maxn],co[2];//vr[] 用来存边，co[]用来存每种颜色的点 
int n,m,u,v,ff;
int color[maxn];
void dfs(int t,int c){
    if(!ff)
        return;
    if(color[t]!=-1){
        if(color[t]!=c)
        // 这个判断不能放在外面if中，会少判断要染的颜色正是想要的时候这种情况 
            ff=0;
            return;
    }
    color[t]=c;
    co[c].push_back(t);
    for(int j=0;j<vr[t].size();j++){
        dfs(vr[t][j],c^1);
    }

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n>>m){
        for(int i=0;i<maxn;i++)
            vr[i].clear();
        co[0].clear();
        co[1].clear();
        mst(color,-1);
        for(int i=0;i<m;i++){
            cin>>u>>v;
            vr[u].push_back(v);
            vr[v].push_back(u);
        }
        ff=1;
        for(int i=1;i<=n&&ff;i++){
            if(color[i]==-1)
            dfs(i,0);
        }
        //cout<<ff<<endl;
        if(!ff)
            cout<<-1<<endl;
        else{
            int cnt=co[0].size();
            cout<<cnt<<endl;
            for(int i=0;i<cnt;i++){
                if(i!=cnt-1)
                    cout<<co[0][i]<<" ";
                else
                    cout<<co[0][i]<<endl;
            }
            cnt=co[1].size();
            cout<<cnt<<endl;
            for(int i=0;i<cnt;i++){
                if(i!=cnt-1)
                    cout<<co[1][i]<<" ";
                else
                    cout<<co[1][i]<<endl;
            }
        }
    }
    return 0;
}

学如逆水行舟，不进则退

最后

以上就是娇气小天鹅为你收集整理的Codeforces Round #360 (Div. 1), problem: (A) NP-Hard Problem（二分图判定+dfs+染色法套用）+ 【二分图简介】的全部内容，希望文章能够帮你解决Codeforces Round #360 (Div. 1), problem: (A) NP-Hard Problem（二分图判定+dfs+染色法套用）+ 【二分图简介】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。