#include <stdio.h>

#define MAX 50010

int parent[MAX];
int relation[MAX];     // 若为 1，表示吃parent; 若为 2，表示被parent吃; 若为 0，表示与跟同类 

int find(int nod)       // 返回nod所在的树的根节点 
{
    int p = parent[nod];
    if(p<0) return nod;       // nod 是根节点 
    while(parent[p]>0)
        p = parent[p];
    return p;
}
int relat_root(int nod)          //返回一个节点与其根与根的关系
{
     int  p, res=0;
     p = parent[nod];

     res += relation[nod];
     while(p>0)
     {
         res += relation[p];
         p = parent[p];
     }                    
     res = res % 3;
     return res;  
}
int relat(int a, int b)    //返回俩个节点的关系
{
      int rel_a, rel_b;   // 分别存放 a, b 与根的关系 
      rel_a = relat_root(a);
      rel_b = relat_root(b);
      
      int relat_ab;
      if(rel_a == rel_b) relat_ab = 0;
      else if(rel_a-rel_b==1 || rel_a-rel_b==-2)  relat_ab = 1;
      else   relat_ab = 2;
      
      return  relat_ab;
}

void merge(int rx, int ry, int rel_x, int rel_y, int d)      // 归并rx和ry两棵树 
{
      if(parent[rx]>=parent[ry])  //树rx的节点数比较少，让rx指向ry 
      {
           parent[ry] += parent[rx];
           parent[rx] = ry;
           if(d==1)
           {
                if(rel_x==rel_y) relation[rx] = 0; 
                else if(rel_x-ry==-1 || rel_x-ry==2)  relation[rx] = 1; 
                else   relation[rx] = 2;
           }
           else // d==2
           {
                if(rel_x==rel_y) relation[rx] = 1;
                else if(rel_x-rel_y==-2 || rel_x-rel_y==1)  relation[rx] = 0;
                else   relation[rx] = 2;
           }                       
      } 
      if(parent[rx]<parent[ry])  //树ry的节点数比较少，让ry指向rx 
      {
           parent[rx] += parent[ry];
           parent[ry] = rx;
           if(d==1)
           {
                if(rel_x==rel_y) relation[ry] = 0; 
                else if(rel_x-rel_y==-1 || rel_x-rel_y==2)  relation[ry] = 2; 
                else   relation[ry] = 1;
           }
           else // d==2
           {
                if(rel_x==rel_y) relation[ry] = 2;
                else if(rel_x-rel_y==-2 || rel_x-rel_y==1)  relation[ry] = 0;
                else   relation[ry] = 1;
           }                       
      }  
}



int main()
{
    int n, d;
    int k, x, y;
    int i, cnt=0;
    
    scanf("%d%d", &n, &k);
    
   	for(i=1;i<=n;i++)
	{
	   parent[i] = -1;
       relation[i] = 0;
	}// initialization
	
    for(i=1; i<=k; i++)
    {
          scanf("%d%d%d", &d, &x, &y);
          if( x>n||y>n ) 
              {      cnt++;  /*printf("LIE: invalid input!  i=%d : cnt=%d\n", i, cnt);*/  continue;      }
          int rx, ry; 
          rx = find(x); // printf("root of x:%d  ", rx);
          ry = find(y); // printf("root of y:%d\n", ry);
         
           if(rx==ry ) 
              { if(relat(x, y) != d-1) { cnt++; /* printf("LIE:i=%d : cnt=%d\n", i, cnt); */} }
          else if(rx!=ry) 
          {
                int rel_x, rel_y;
                rel_x = relat_root(x);
                rel_y = relat_root(y);
                
                merge(rx, ry, rel_x, rel_y, d);
          }
                            
    }
    printf("%d", cnt);
    return 0;    
}

• Re:求教各位高手指点迷津，我的代码（有注释）总是wa,给点测试数据也行啊 (92) jmh617 2008-07-30 16:23:32