并查集练习---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); 
    } 
} 

补充：软件开发 , C++ ,

上一个：poj_1041 John's trip
下一个：并查集练习---poj 1417 并查集+DP