POJ2912(Rochambeau)

链接：https://vjudge.net/problem/POJ-2912
思路：这个题有点意思，如果不是放在并查集专题真不一定会往这个方向去想，首先如果一个人是裁判当且仅当除了他以外的所有人没矛盾以及包括他在内的所有人存在矛盾。所以当除开裁判外所有人的关系是满足模3加法的传递性的，所以我们考虑枚举所有可能为裁判的人，除开他之外所有人维护一个并查集并寻找是否有错误，如果没有的话更新答案，如果存在两个这样的人就不能判断出谁是裁判，如果不存在就无解，否则的话在最后一个矛盾出现的地方就是能判断出裁判的地方（这个地方有些争议，不过因为这个是题意问题就这样吧）
代码：

#include<algorithm>
#include<cstring>
using namespace std;

const int maxn = 5000;
int par[maxn];
int rel[maxn];
int n,m;

int getroot(int a){
    if(par[a]==a)return a;
    int px = par[a];
    par[a] = getroot(par[a]);
    rel[a] = (rel[a]+rel[px]+3)%3;
    return par[a];
}

struct con{
    int u,v,w;
}ss[maxn];

char ch[1000];

int main(){
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<m;i++){
            int a,b;
            char c;
            scanf("%d%c%d",&a,&c,&b);
            int r;
            if(c=='>') r = 1;
            else if(c=='<')r = 2;
            else r = 0;
            ss[i].u = a;
            ss[i].v = b;
            ss[i].w = r;
        }
        int nowi = -1;
        int resj = -1;
        int tmp = -1;
        int j;
        int flag = 1;
        for(int i=0;i<n;i++){
            for(int jj=0;jj<=n;jj++){
                par[jj] = jj;
                rel[jj] = 0;
            }
            tmp = -1;
            for(j=0;j<m;j++){
                if(ss[j].u==i||ss[j].v==i)continue;
                int u = ss[j].u;
                int v = ss[j].v;
                int p1 = getroot(u);
                int p2 = getroot(v);
                if(p1==p2&&((rel[u]-rel[v]+3)%3)!=ss[j].w){
                    tmp = j;
                    break;
                }
                else if(p1!=p2){
                par[p2] = p1;
                rel[p2] = (-rel[v]-ss[j].w+rel[u]+6)%3;
                }
            }
        if(j==m){//发现一个新成立的答案
            if(nowi!=-1){//如果已经有答案存在
                printf("Can not determine\n");
                flag = 0;
                break; 
            }
            else nowi = i;//没有的话更新答案
        }
        else resj = max(resj,tmp);//更新最后一个矛盾出现的地方
        }
        if(!flag)continue;
        if(nowi!=-1){
        printf("Player %d can be determined to be the judge after %d lines\n",nowi,resj+1);
        }
        else printf("Impossible\n");
    }
    return 0;
}
~