并查集的Union操作，作用是把两个等价关系的节点的祖先节点合并。
但是现在给出的每组数据里，两个节点可能不是属于同一个集合，所以需要用偏移量来搞（呃，我自己怎么叫它，不知道正规术语怎么叫）。
在结构体里开一个ki域，用来存当前节点同父节点的偏移量，如果是同类偏移0，天敌偏移1，猎物偏移-1（%3=2）。
所以，每次find和union操作都要更新当前节点同新的父节点的关系，根节点的父节点为自己，所以偏移量始终为0。
难点应该在于合并两棵树的情况，用递归写find，先确定父节点再确定当前节点的ki值。
以下代码，295MS：
各位WA的童鞋，输入只有单组数据，写成while(scanf("%d %d",&n,&k)!=EOF)的会WA

#include<iostream>
#define SIZE 50010
using namespace std;
int n,k;
int d,x,y;
struct node
{
    int pa;
    int ki;
}a[SIZE];
void Init(int n)
{
    for(int i=1;n-i>=0;i++)
    {
        a[i].pa=i;
        a[i].ki=0;
    }
}
int findPa(int n)
{
    if(a[n].pa!=n)
    {
        int Pa=a[n].pa;
        int Root=findPa(a[n].pa);
        a[n].ki=(a[n].ki+a[Pa].ki+3)%3;
        return a[n].pa=Root;
    }
    else return n;
}
void Union(int x,int y,int del)
{
    int xx=findPa(x);
    int yy=findPa(y);
    a[xx].pa=yy;
    a[xx].ki=(a[y].ki-(a[x].ki+del)+3)%3;
}
int main()
{
    scanf("%d %d",&n,&k);
    Init(n);
    int wrong=0;
    for(int i=0;k-i>0;i++)
    {
        scanf("%d %d %d",&d,&x,&y);
        if(x>n||y>n) wrong++;
        else if(x==y&&d==2) wrong++;
        else 
        {
            int xx=findPa(x);
            int yy=findPa(y);
            if(xx==yy)
            {
                if(d==1&&(a[x].ki!=a[y].ki)) wrong++;
                if(d==2&&(a[y].ki-a[x].ki+3)%3!=1) wrong++;
            }
            else
            {
                Union(x,y,d-1);
            } 
        }
    }
    printf("%d\n",wrong);
    //system("pause");
    return 0;
}

• Re:一些想法，附代码 (9) qiyifeijiayou 2011-11-20 14:19:28