c++實例研究

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

well 代碼分格越來越簡練，明了。
less well 較費時的地方：合并根結點計算相對偏移。mod運算結果是負數(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;
}