poj 2912 并查集（食物链加强版）

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <algorithm>
  4 #include <iostream>
  5 using namespace std;
  6 const int MAXN=510;
  7 const int MAXM=2010;
  8 struct Node
  9 {
 10     int u,v;
 11     int re;
 12 }node[MAXM];
 13 int F[MAXN];
 14 int val[MAXN];
 15 int find(int x)
 16 {
 17     if(F[x]==-1)return x;
 18     int tmp=find(F[x]);
 19     val[x]+=val[F[x]];
 20     val[x]%=3;
 21     return F[x]=tmp;
 22 }
 23 char str[30];
 24 int main()
 25 {
 26     int n,m;
 27     int u,v;
 28     while(scanf("%d%d",&n,&m)==2)
 29     {
 30         gets(str);
 31         for(int i=0;i<m;i++)
 32         {
 33             //scanf("%s",&str);
 34             gets(str);
 35             int t=0;
 36             int len=strlen(str);
 37             for(t=0;t<len;t++)
 38               if(str[t]==‘>‘||str[t]==‘=‘||str[t]==‘<‘)
 39                 break;
 40             u=0;
 41             for(int j=0;j<t;j++)
 42             {
 43                 u*=10;
 44                 u+=str[j]-‘0‘;
 45             }
 46             v=0;
 47             for(int j=t+1;j<len;j++)
 48             {
 49                 v*=10;
 50                 v+=str[j]-‘0‘;
 51             }
 52             node[i].u=u;
 53             node[i].v=v;
 54             if(str[t]==‘=‘)node[i].re=0;
 55             else if(str[t]==‘<‘)node[i].re=1;
 56             else node[i].re=2;
 57         }
 58         int ansi;
 59         int anst=0;
 60         int t0=0;//不矛盾的个数
 61         for(int i=0;i<n;i++)
 62         {
 63             memset(F,-1,sizeof(F));
 64             memset(val,0,sizeof(val));
 65             int ff=-1;
 66             for(int j=0;j<m;j++)
 67             {
 68                 if(node[j].u==i || node[j].v==i)continue;
 69                 u=node[j].u;
 70                 v=node[j].v;
 71                 int t1=find(u);
 72                 int t2=find(v);
 73                 if(t1==t2)
 74                 {
 75                     if(val[v]!=(val[u]+node[j].re)%3)
 76                     {
 77                         ff=j+1;
 78                         break;
 79                     }
 80                 }
 81                 else
 82                 {
 83                     F[t2]=t1;
 84                     val[t2]=val[u]-val[v]+node[j].re;
 85                     val[t2]=(val[t2]+3)%3;
 86                 }
 87             }
 88             if(ff==-1)
 89             {
 90                 ansi=i;
 91                 t0++;
 92             }
 93             else anst=max(anst,ff);
 94         }
 95         if(t0==0)printf("Impossible\n");
 96         else if(t0>=2)printf("Can not determine\n");
 97         else
 98            printf("Player %d can be determined to be the judge after %d lines\n",ansi,anst);
 99     }
100     return 0;
101 }