首页 > 代码库 > hdu 4751 Divide Groups 二分图

hdu 4751 Divide Groups 二分图

2024-07-11 13:36:23   223人阅读

题意给出所有人之间的关系，单向的，问能不能将这群人分成两组，使得每组内部的任意两人都互相认识。

先把单向边都换成无向边，即如果a，b互相认识那么不变，如果只是单向边的话那么则认为他们两个不认识，然后假设能分成满足题意的两个集合，那么新图的补图中这两个集合内部是没有边的，所以只要判断补图是不是二分图即可。

#include <cstdio>#include <cstring>#include <queue>using namespace std;int G[210][210];int color[210];int n;int bfs(int x){    queue <int> Q;    Q.push(x);    color[x]=0;    while(!Q.empty())    {        x=Q.front();Q.pop();        for(int i=1;i<=n;i++)        {            if(i==x||G[x][i]==1) continue;            if(color[i]==-1)            {                color[i]=color[x]^1;                Q.push(i);            }            else if(color[i]==color[x]) return 0;        }    }    return 1;}int main(){    while(scanf("%d",&n)!=EOF)    {        int i,j,x;        memset(G,0,sizeof(G));        for(i=1;i<=n;i++)        {            scanf("%d",&x);            while(x!=0)            {                G[i][x]=1;                scanf("%d",&x);            }        }        for(i=1;i<=n;i++)            for(j=1;j<=n;j++)                if(G[i][j]==0)                    G[j][i]=0;        memset(color,-1,sizeof(color));        int flag=1;        for(i=1;i<=n;i++)            if(color[i]==-1)                if(bfs(i)==0)                {                    flag=0;                    break;                }        if(flag) printf("YES\n");        else printf("NO\n");    }    return 0;}
View Code

 


联系
我们