c++實例研究

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

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