Divide Groups(hdu4751)(二分图判定)
程序员文章站
2022-03-03 11:34:54
...
[原题链接!](http://acm.hdu.edu.cn/showproblem.php?pid=4751
题意:
其实这个题最难懂的是题意orz(嘤语菜真的难受)
告诉你n个人的关系:第i行表示第i个人认识那些人,以0结尾。
求这n个人能否被分成两组,每一组的人都互相认识。
即任意选出一个人,他必须认识当前组的其他所有人,其他人也要认识他。
必须两个人互相认识才算他们认识(单相思没*),
并且认识是没有传递性的(a认识b,b认识c,不代表a认识c。
思路:
弄懂题意就好做了,这就是一个二分图的判定(二分图匹配算法可参考白皮p97),注意要把单相思(雾)的去掉。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int map[300][300],col[300],n,flag;
void dfs(int a,int c)
{
if(flag)
return;
if(col[a]==0)
col[a]=c;
for(int i=1;i<=n;i++){
if(map[a][i]==0)
{
if(col[i]==0)
dfs(i,-c);
else if(col[i]==col[a])
{
flag=1;
return;
}
}
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
int x;
memset(map,0,sizeof(map));
memset(col,0,sizeof(col));
for(int i=1;i<=n;i++){
while(scanf("%d",&x)&&x)
{
map[i][x]=1;
//cout<<x<<endl;
}
}
for(int i=1;i<n+1;i++)
for(int j=1;j<n+1;j++){
if(map[i][j]==0||map[j][i]==0) //去掉不是互相认识的
map[i][j]=map[j][i]=0;
if(i==j)
map[i][j]=1;
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// cout<<map[i][j]<<" ";
// }
// cout<<endl;
// }
flag=0;
for(int i=1;i<n+1;i++){ //dfs二分图匹配
if(!col[i])
dfs(i,1);
}
if(flag)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}