欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}
相关标签: 图论