所谓二分图,即可以把途中所有的点分成两类,满足关系是在同一类的点之间一定没有相连的边,不在同一类的点之间可以有相连的边。注意是可能有,不是一定都要有,且只能有两类不能有多类。

染色法基于一个定理,即奇数点构成的环一定不是二分图,证明:假如是同一类的两个同类的点相连,则在环除了这两个点以外的点,应该都满足交叉的,则必定会有奇数个,再加上这两个点,一共是奇数个点,因此一定不是二分图。

染色法具体的思路:

对于每个点进行判断,若当前的点未染色,则染成一个颜色,然后对于相连接的点,都染成另一种颜色,若有相连的点已经有颜色,则进行判断,若是同一种颜色则不是二分图,返回false,若所有点染色都成功,则是二分图,返回true。循环是看是否所有点染色都成功,只要其中一次染色失败就是false。这所以这样做,是因为有些点之间可能不存在通路,所以要对所有点都进行染色。

#include<iostream>
#include<cstring>

using namespace std;
const int N=1000010;
int h[N],e[N],idx=0,ne[N];
int col[N];
int m,n;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool dye(int x,int c)
{   
 
    col[x]=c;
    for(int j=h[x];j!=-1;j=ne[j])
    {
        int t=e[j];
        if(!col[t])
        {
            if(!dye(t,3-c))
            {
                return false;
            }
        }
        else
        {
            if(col[t]!=3-c)
            return false;
        }
    }
    return true;
}

int main()
{   
   memset(h,-1,sizeof h);
   scanf("%d%d",&n,&m);
   while(m--)
   {
       int a,b;
       scanf("%d%d",&a,&b);

       add(a,b),add(b,a);
   }
   
   bool t=false;
   for(int i=1;i<=n;i++)
   {   
       if(!col[i])
        if(!dye(i,1))
        {   
            t=true;
            break;
        }
   }
   
   if(t)puts("No");
   else puts("Yes");
   
    return 0;
}

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部