POJ 1182 解题报告－－【附】注释对oj的影响

该题的解题关键是：
1、将解题的主要流程画出来：
如果d==1,那么 如果find(x)==find(y) ，则：
                         else: union()
如果d==2,那么，如果find(x)==find(y),则：判断
                         else:union()
2、判断的时候，如果d==1，那么只要relation(x)==relation(y)，即可
                           如果d==2, 那么需要一个关系式来判定：
                                                        A
                                                  x          y
                           首先，因为x,与 y的关系已经有输入确定了，x吃y,那么 ，x与A的关系，y与A的关系也定了，因此，找个式子判断这三个关系组合在一起成立不成立就可以了。呵呵，貌似很简单，可是在想这道题目的时候是多么的抓狂！relation[x]==(relation[y]+1)%3,这样，输入才正确。
附注：如果题目中没有注释，可以减少运行的时间，看图：呵呵

#include <iostream>
//#include <string.h>
//#include <stdlib.h>
//#include <time.h>
using namespace std;
int num;
int parent[50001];
int rel[50001];
//int check[100000];
int digui(int x);
int find(int x)
{
int a=x;
while(parent[a]!=a)
   a=parent[a];
//将x保存
// int z=x;
while(parent[x]!=x)
{
   int temp=parent[x];
   rel[x]=digui(x);
   parent[x]=a;
   x=temp;
}
return a;
}
int digui(int x)
{
if(parent[x]==x)
return 0;
else
return ((rel[x]+digui(parent[x]))%3);
}
void unionrel(int a,int b,int d)
{
int x=find(a);
int y=find(b);
parent[x]=y;
rel[x]=((3-rel[a]+d+rel[b]))%3;
/*
细节决定成败：
这里：最开始我写为：
parent[a]=b;//这个显然是错误的,应该是a的根节点指向b的根节点，即：parent[find(a)]=find[b]
rel[a]= ((3-rel[a]+d+rel[b]))%3;//把rel[a]重新定义为：((3-rel[a]+d+rel[b]))%3 这也是不对的，应该是rel[parent[a]]
*/
}
int main()
{
// clock_t start=clock();
// memset(check,0,sizeof(check));
int m,n;
// cin>>m>>n;//m:动物的个数 n:n种关系
scanf("%d%d",&m,&n);
// FILE *fp;
// fp=fopen("input.in","r");
// fscanf(fp,"%d%d",&m,&n);
int i=0;
for(i=1;i<=m;i++)
{
   parent[i]=i;
   rel[i]=0;
}
for(i=1;i<=n;i++)
{//开始接受n条关系了
   int d,x,y;
   scanf("%d%d%d",&d,&x,&y);
// cin>>d>>x>>y;//2 1 2
// fscanf(fp,"%d%d%d",&d,&x,&y);
   if(x>m||y>m)
   {
   
    num++;
//   check[i]=1;
    continue;
   }
  
   if(d==2&&x==y)
   {
    num++;
//   check[i]=1;
    continue;
   }

   if(d==1)
   {//同类动物
    if(find(x)==find(y))
    {
     if(rel[x]!=rel[y])
     {
      num++;
//     check[i]=1;
     // continue;
     }
    
    }
    else
    {
     unionrel(x,y,0);//将x,y建立为同一种关系
    }
   
   }
   else //if(d==2)
   {
    if(find(x)==find(y))
    {
     if(rel[x]!=(rel[y]+1)%3)
     {
      num++;
//     check[i]=1;
     // continue;
     }
    
    }
    else
    {
     unionrel(x,y,1);//将x,y建立为敌人关系
    }
   
   }    
}
cout<<num<<endl;
// cout<<"谎话总数"<<num<<endl;
// int test=1;
/*
while(test<=i)
{
   if(check[test]!=0)
   cout<<"第"<<test<<"条"<<endl;
   test++;
}
*/
// cout<<clock()-start<<endl;
// system("PAUSE");
return 0;
}