题目大意：判断一堆人能否分成两组，组内人都互相认识。
思路：不认识的人一定不在一起！
#include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<cmath> #include<string> #include<cstring> #include<set> #include<map> #include<list> #include<queue> #include<vector> #define tree int o,int l,int r #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define lo o<<1 #define ro o<<1|1 #define ULL unsigned long long #define LL long long #define inf 0x7fffffff #define eps 1e-7 #define M 9901 #define N 109 using namespace std; int T,n,m,k,t; int f[N],h[N],val[N]; int find(int x) { if(f[x]!=x) { int tou=f[x]; f[x]=find(f[x]); val[x]=(val[x]+val[tou])%2; } return f[x]; } int main() { #ifndef ONLINE_JUDGE freopen("ex.in","r",stdin); #endif vector<int>g[N]; while(scanf("%d",&n)==1) { for(int i=0;i<=n;i++) { g[i].clear();//WA f[i]=i; val[i]=0; } for(int i=1; i<=n; i++) { memset(h,0,sizeof(h)); h[i]=1; while(1) { int t; scanf("%d",&t); if(!t)break; h[t]=1; } for(int j=1; j<=n; j++) if(!h[j]) { g[i].push_back(j); } } int ok=1; for(int i=1;i<=n&&ok;i++) { for(int j=0;j<g[i].size();j++) { int u=i,v=g[i][j]; int toux=find(u); int touy=find(v); if(toux!=touy) { int g=val[u]+val[v]+1; g%=2; f[touy]=toux; val[touy]=g; } else { int g=val[u]+val[v]; g%=2;//WA if(g!=1) { ok=0;break; } } } } printf("%s ",ok?"YES":"NO"); } return 0; }