並查集練習---poj 2912

集合的合並與維護和食物鏈那道題一樣。

不過多了個裁判。注意到N<=500，所以可以枚舉裁判，然後判斷是否出現了矛盾。（忽略裁判）

如果有矛盾，則這個人不是裁判。

唯一有點難度的是輸出第幾行判斷出的裁判。

原先以為是最後出現裁判的那一行。

後來發現應當時枚舉其他人時候首次出現矛盾的最大值。（仔細想想)

這樣這道題就解決了。

【代碼】

[cpp] 
#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); 
    } 
}