本文共 1151 字，大约阅读时间需要 3 分钟。

题目大意

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

题解

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

dfs解法

/*    二分图，dfs染色     用vector数组存每个点的相邻的点，    先将每个点的颜色标为-1，再逐个遍历，    每当找到一个点的颜色是-1时，dfs将其及其相邻点染色；    如果染色时发现该点已经染色了，则须进行判断    1,如果该点的颜色与想给它染的颜色相同，则直接返回（对于写法要注意，刚开始判断放在外面，造成了死循环）     2，如果该点的颜色与想染的颜色不同，则说明产生了矛盾，及该图不能成为二分图，标记并返回     最后打印就好 */#include
   
    #define mst(a,b) memset(a,b,sizeof(a))using namespace std;const int maxn=1e5+10;vector
    
      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
     
      >n>>m){
           for(int i=0;i
      
       >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<
       
        <
       
      
     
    
   

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/100898598 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！