并查集,以及可拆分并查集

 1 //常用版本
 2 
 3 //Union Find
 4 int f[1005000];
 5 
 6 void INIT(int size)
 7 { for(int i=0;i<=size;i++) f[i]=i; }
 8 
 9 int findf(int x) 
10 { return f[x]==x ? x : f[x]=findf(f[x]); };
11 
12 int connect(int x)
13 { f[findf(a)]=findf(b); }

 1 //可拆分版本
 2 //Union Find
 3 int f[1005000];
 4 
 5 void INIT(int size)
 6 { for(int i=0;i<=size;i++) f[i]=i; }
 7 
 8 int findf(int x)
 9 { for(;x!=f[x];x=f[x]); }
10 
11 void setroot(int x)
12 { if(f[x]!=x) setroot(f[x]); f[x]=f[f[x]]=x; }
13 
14 inline void link(int x,int y)
15 { setroot(x); f[x]=y; }
16  
17 inline void cut(int x,int y)
18 { setroot(x); f[y]=y; }