NOI的题目，并查集的高级应用，很好玩的一个题目。题目：http://acm.pku.edu.cn/JudgeOnline/problem?id=1182

#include "stdio.h"
int num[50005];
int dis[50005];
int relation1[3]={0,1,2}; /*正权*/
int relation2[3]={0,2,1}; /*负权*/
void make(int p)
{
    int i;
    for(i=0;i<p;i++)
    {
        num[i]=-1;
        dis[i]=0;
    }
}
int find(int p)
{
    int i;
    if(num[p]<0)return p;
    i=find(num[p]);
    dis[p]=dis[p]+dis[num[p]];
    num[p]=i;
    return i;
}
void un(int a,int b,int len)
{
    int ra=find(a);
    int rb=find(b);
    num[rb]=ra;
    dis[rb]=dis[a]+len-dis[b];
}
int main()
{
    int n,k,i;
    int x,y,d;
    int rx,ry;
    int dx,dy;
    int count;
    scanf("%d%d",&n,&k);
    make(n);count=0;
    for(i=0;i<k;i++)
    {
        scanf("%d%d%d",&d,&x,&y);
        if(x>n||y>n)count++;
        else
        {
            rx=find(x-1);
            ry=find(y-1);
            if(d==1)
            {
                if(rx!=ry)un(x-1,y-1,0);
                else
                {
                    if(dis[x-1]<0)dx=relation2[(-dis[x-1])%3];
                    else dx=relation1[dis[x-1]%3];
                    if(dis[y-1]<0)dy=relation2[(-dis[y-1])%3];
                    else dy=relation1[dis[y-1]%3];
                    if(dx!=dy)count++;
                }
            }
            else
            {
                if(rx!=ry)un(x-1,y-1,1);
                else
                {
                    if(dis[x-1]<0)dx=relation2[(-dis[x-1])%3];
                    else dx=relation1[dis[x-1]%3];
                    if(dis[y-1]<0)dy=relation2[(-dis[y-1])%3];
                    else dy=relation1[dis[y-1]%3];
                    if((dx+1)%3!=dy)count++;
                }
            }
        }
    }
    printf("%d\n",count);
    return 0;
}