好久沒(méi)有ACM，對(duì)很多地方都有膽怯，看著并查集資料，這道題摸索了4個(gè)小時(shí)，可見編碼能力有待大幅提高。
首先想到思路無(wú)疑是按題目中A,B,C分類方式，維護(hù)多個(gè)集合，再判斷集合關(guān)系，適當(dāng)合并。這種做法很直觀，但卻很麻煩。麻煩主要出現(xiàn)在維護(hù)集合間關(guān)系。當(dāng)兩個(gè)集合合并后，與合并集合相關(guān)集合的關(guān)系需要遞歸的維護(hù)。例如A-B, C-D,合并A,C后，B,D也需要合并。以元素抽象的集合操作麻煩。最后看題解上，維護(hù)的是有關(guān)系元素的集合，而不是同類型元素集合，并在關(guān)系集的結(jié)點(diǎn)中用相對(duì)偏移維護(hù)結(jié)點(diǎn)和根關(guān)系。合并時(shí)，更新根結(jié)點(diǎn)關(guān)系，并在查找時(shí)更新結(jié)點(diǎn)關(guān)系。詳細(xì)內(nèi)容都可參考網(wǎng)絡(luò)上大部分實(shí)現(xiàn)。
理解了這種做法后，我不想用路徑壓縮，而想用相對(duì)關(guān)系樹來(lái)做。合并時(shí)更新作為孩子的結(jié)點(diǎn)的關(guān)系偏移量，在判斷關(guān)系時(shí)通過(guò)遍歷從結(jié)點(diǎn)到根的關(guān)系偏移量得到結(jié)點(diǎn)和總的根結(jié)點(diǎn)關(guān)系。

well 代碼分格越來(lái)越簡(jiǎn)練，明了。
less well 較費(fèi)時(shí)的地方：合并根結(jié)點(diǎn)計(jì)算相對(duì)偏移。mod運(yùn)算結(jié)果是負(fù)數(shù)。差錯(cuò)用了不少時(shí)間。

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 50001

typedef struct _Node{
    int p;
    int r;
}Node;

Node elem[MAXSIZE];
int N,K;

void initial()
{
    int i;
    for(i=1;i<=N;i++)
    {
        elem[i].p=i;
        elem[i].r=0;
    }
}

int find(int x)
{
    while(x!=elem[x].p)
        x = elem[x].p;
    return x;
}

int relation(int x)
{
    int r=0;
    while(x!=elem[x].p){
        r += elem[x].r;
        x = elem[x].p;
    }
    return r%3;
}

int merge(int x, int y, int px, int py, int type)
{
    elem[px].r = (relation(y)-type-relation(x)+3)%3;
    elem[px].p = py;
}

int judge(int t,int x,int y)
{
    int px,py;

    if((x>N)||(y>N)) return 0;
    if(t==1)
    {
        px = find(x);
        py = find(y);
        if(px!=py) {merge(x,y,px,py,0); return 1;}
        return (relation(x)==relation(y));
    }
    else
    {
        px = find(x);
        py = find(y);
        if(px!=py) {merge(x,y,px,py,1); return 1;}
        //printf("%d==%d\n", ( relation(x)+1 ) %3, relation(y));
        return ( (( relation(x)+4) %3)  ==  relation(y)  );
    }
}

int main()
{
    int t, x, y;
    int i,j;
    int w;
    
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    
    scanf("%d%d",&N,&K);
    initial();

    
    w=0;
    for(i=0;i<K;i++)
    {
        scanf("%d%d%d",&t,&x,&y);
        if(!judge(t,x,y))
        {
            //printf("t:%d,x:%d,y:%d\n",t,x,y);
            //for(j=1;j<=5;j++)
            //{
            //    printf("j=%d,p=%d,r=%d\n",j,elem[j].p,elem[j].r);
            //}
            w++;
        }
    }
    printf("%d\n",w);
    return 0;
}