一道很简单的题，不过在比赛的时候没有写出来；
刚刚看到这个题，我以为是一个图论题，后来发现其实就是一个暴力的题；
用bfs，因为一个人与他不认识的人肯定不会在一个集合，如果判断出现冲突则分配失败，否则就成功；
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define maxn 103 5 using namespace std; 6 7 int map[maxn][maxn],n; 8 int b[maxn]; 9 10 bool bfs(int a) 11 { 12 queue<int>q; 13 q.push(a); 14 while(!q.empty()) 15 { 16 int u=q.front(); 17 q.pop(); 18 for(int i=1; i<=n; i++) 19 { 20 if(i==u||(map[u][i]&&map[i][u]))continue; 21 if(b[i]==-1) 22 { 23 b[i]=b[u]^1; 24 q.push(i); 25 } 26 else if(b[i]==b[u]) return 1; 27 } 28 } 29 return 0; 30 } 31 int main() 32 { 33 int a; 34 while(scanf("%d",&n)!=EOF) 35 { 36 memset(map,0,sizeof map); 37 for(int i=1; i<=n; i++) 38 { 39 while(scanf("%d",&a)&&a) 40 map[i][a]=1; 41 } 42 memset(b,-1,sizeof b); 43 int i; 44 for(i=1; i<=n; i++) 45 { 46 if(b[i]==-1) 47 { 48 b[i]=0; 49 if(bfs(i)) break; 50 } 51 } 52 if(i==n)puts("YES"); 53 else puts("NO"); 54 } 55 return 0; 56 }