并查集结构:

for 

(i = 0; i <= n; ++i)

 

f[i] = i;

查找祖先：

int 

find(

int 

x)

{

    

if 

(x != f[x])

    

{

        

f[x] = find(f[x]);

    

}

    

return 

f[x];

}

合并操作：

经常使用的：

void 

Union(

int 

x,

int 

y)

{

    

x = find(x);

    

y = find(y);

    

if 

(x != y)

    

{

        

f[y] = x;

        

num[x] += num[y];

//根记录子系的个数

    

}

}

还有一种写法：

void 

Union(

int 

root1,

int 

root2)

{

     

int 

x = FindSet(root1), y = FindSet(root2);

     

if

( x == y )

return 

;

     

if

( rank[x] > rank[y] ) parent[y] = x;

     

else

{

         

parent[x] = y;

         

if

( rank[x] == rank[y] ) ++rank[y];

     

}

}