并查集练习---poj 2912
集合的合并与维护和食物链那道题一样。
不过多了个裁判。注意到N<=500，所以可以枚举裁判，然后判断是否出现了矛盾。（忽略裁判）
如果有矛盾，则这个人不是裁判。
唯一有点难度的是输出第几行判断出的裁判。
原先以为是最后出现裁判的那一行。
后来发现应当时枚举其他人时候首次出现矛盾的最大值。（仔细想想)
这样这道题就解决了。
【代码】
#include <iostream>#include <cstring>#include <string>#include <cstdio>#include <algorithm>using namespace std;const int N=505,M=2005;int fa[N],r[N],x[M],y[M],z[M];int n,m,k,kk,ans;int find(int x){ if (fa[x]==x) return x; int t=fa[x]; fa[x]=find(fa[x]); r[x]=(r[x]+r[t])%3; return fa[x];}int main(){ int i,j,fx,fy; bool ff; char c; freopen("in","r",stdin); while (scanf("%d%d",&n,&m)!=EOF) { for (i=1;i<=m;i++) { scanf("%d%c%d",&x[i],&c,&y[i]); if (c=='<') z[i]=2; else if (c=='>') z[i]=1; else z[i]=0; } ans=k=kk=0; for (j=0;j<n;j++) { ff=true; for (i=0;i<n;i++) { fa[i]=i; r[i]=0; } for (i=1;i<=m;i++) { if (x[i]==j || y[i]==j) continue; fx=find(x[i]);fy=find(y[i]); if (fx!=fy) { fa[fy]=fx; r[fy]=(r[x[i]]-r[y[i]]-z[i]+6)%3; } else if ((r[x[i]]-r[y[i]]+3)%3!=z[i]) { ff=false; kk=max(kk,i); break; } } if (ff) { ans++;k=j; if (ans>1) break; } } if (ans==0) printf("Impossible\n"); else if (ans>1) printf("Can not determine\n"); else printf("Player %d can be determined to be the judge after %d lines\n",k,kk); }}