好久沒有ACM，對(duì)很多地方都有膽怯，看著并查集資料，這道題摸索了4個(gè)小時(shí)，可見編碼能力有待大幅提高。
首先想到思路無疑是按題目中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)系樹來做。合并時(shí)更新作為孩子的結(jié)點(diǎn)的關(guān)系偏移量，在判斷關(guān)系時(shí)通過遍歷從結(jié)點(diǎn)到根的關(guān)系偏移量得到結(jié)點(diǎn)和總的根結(jié)點(diǎn)關(guān)系。
well 代碼分格越來越簡練，明了。
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;
}