DSL_1_A Set - Disjoint Set: Union Find Tree
問題
互いに素な集合 Union Find| データ構造ライブラリ | Aizu Online Judge
テキトーに配列で実装したら、案の定時間切れ。
調べてみると、こんな解法があるらしい。
www.slideshare.net
先人の知恵をありがたく拝借し、実装。経路圧縮のみ。
#include<stdio.h> #define MAX 10000 typedef struct node{ int id; int rootid; struct node *up; }node; int Getrootid(node N[],int x){ node *p; if(N[x].up==NULL)N[x].rootid=x; else{ p=N[x].up; while(p->up != NULL)p=p->up; N[x].rootid=p->id; N[x].up=p; } return N[x].rootid; } int main(){ int n,q,i; int com; int x,y; node N[MAX]; scanf("%d %d",&n,&q); for(i=0;i<n;i++){ N[i].id=i; N[i].rootid=-1; N[i].up=NULL; } for(i=0;i<q;i++){ scanf("%d",&com); if(com==0){/*unite*/ scanf("%d %d",&x,&y); N[x].rootid=Getrootid(N,x); N[y].rootid=Getrootid(N,y); if(N[x].rootid != N[y].rootid) N[ N[x].rootid ].up=&(N[ N[y].rootid ]); } else if(com==1){/*same*/ scanf("%d %d",&x,&y); N[x].rootid=Getrootid(N,x); N[y].rootid=Getrootid(N,y); if(N[x].rootid==N[y].rootid) printf("1\n"); else printf("0\n"); } } return 0; }
ルートが同じノード同士のuniteで不都合が生じた。ルートのノードが持つポインタが、自分を指すようになり、sameでループから抜け出せなくなってしまった。ifで対応。