并查集概念：
并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
集合通用表示方法:
typedef struct{
ElementType Data;
int Parent;
}SetType;
寻找集合中的根节点（Find函数）：
int Find(SetType S[], ElementType x){
int i;
for(i=0; i<MaxSize && S[i]!=x; i++); //线性搜索
if(i>=MaxSize) return -1;
for(;S[i].Parent>=0;i=S[i].Parent);
return i;
}
集合的并运算（Union函数）：
void Union(SetType S[], ElementType X1, ElementType X2){ //根节点Parent默认为-1
int Root1, Root2;
Root1 = Find(S,X1);
Root2 = Find(S,X2);
if(Root1 != Root2) S[Root2].Parent = Root1;
}
并运算优化（根节点Parent值为集合元素个数的负数）：
按秩归并比规模
void Union( SetType S, SetName Root1, SetName Root2 ){ //Root1和Root2是不同集合的根结点
if ( S[Root2] < S[Root1] ) { //小集合并入大集合
S[Root2] += S[Root1];
S[Root1] = Root2;
}
else {
S[Root1] += S[Root2];
S[Root2] = Root1;
}
}
例题：File Transfer
We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?
Input Specification:
Each input file contains one test case. For each test case, the first line contains N (2≤N≤104), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:
I c1 c2
where
I
stands for inputting a connection between
c1
and
c2
; or
C c1 c2
where
C
stands for checking if it is possible to transfer files between
c1
and
c2
; or
S
where
S
stands for stopping this case.
Output Specification:
For each
C
case, print in one line the word “yes” or “no” if it is possible or impossible to transfer files between
c1
and
c2
, respectively. At the end of each case, print in one line “The network is connected.” if there is a path between any pair of computers; or “There are
k
components.” where
k
is the number of connected components in this network.
Sample Input 1:
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S
Sample Output 1:
no
no
yes
There are 2 components.
Sample Input 2:
5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
I 1 3
C 1 5
S
Sample Output 2:
no
no
yes
yes
The network is connected.
Demo:
因为电脑被由1到N的整数表示，因此可以省略结构体中Data域，利用下标表示Data域的值。
#include<iostream>
using namespace std;
void Initialization(int S[],int n){ //初始化集合，所有结点都作为根结点
for(int i=0;i<n;i++)
S[i]=-1;
}
int Find(int S[], int x){ //搜索根结点
for(;S[x]>=0;x=S[x]);
return x;
}
void Union(int S[], int Root1, int Root2){ //连接集合树
S[Root2] = Root1;
}
void Input_connection(int S[]){ //连接两台电脑
int u,v;
int Root1,Root2;
cin>>u>>v;
Root1 = Find(S,u-1);
Root2 = Find(S,v-1);
if(Root1 != Root2)
Union (S,Root1,Root2);
}
void Check_connection(int S[]){ //判断两台电脑之间是否连接
int u,v;
int Root1,Root2;
cin>>u>>v;
Root1 = Find(S,u-1);
Root2 = Find(S,v-1);
if(Root1 == Root2)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
void Check_network(int S[],int n){ //判断集合个数
int i,connect = 0;
for(i=0;i<n;i++){
if(S[i]<0) connect++;
}
if(connect == 1)
cout<<"The network is connected."<<endl;
else
cout<<"There are "<<connect<<" components."<<endl;
}
int main(){
int S[10001];
int n;
char ch;
cin>>n;
Initialization(S,n);
do{
cin>>ch;
switch(ch){
case 'I':Input_connection(S); break;
case 'C':Check_connection(S); break;
case 'S':Check_network(S,n); break;
}
}while(ch != 'S');
return 0;
}
优化（按秩归并、路径压缩）：
按秩归并对Union函数优化，路径压缩对Find函数优化
按秩归并
：比树高、比规模
最坏情况树高O(log N)
比树高：矮树向高树并
S[Root]=
–
树高
if(S[Root2] < S[Root1])
S[Root1] = Root2;
else{
if(S[Root1]==S[Root2]) Root1--;
S[Root2] = Root1;
}比规模：小树向大树并
S[Root]=
–
元素个数
if ( S[Root2] < S[Root1] ) {
S[Root2] += S[Root1];
S[Root1] = Root2;
}
else {
S[Root1] += S[Root2];
S[Root2] = Root1;
}
路径压缩
：
SetName Find(SetType S,ElementType X){
if(S[X] < 0) return X;
else
return S[X] = Find(S,S[X]);
}伪递归，将自身及路径上的结点的父节点均改为根结点
路径压缩和按高度归并都会影响树的高度，因此路径压缩一般配合按规模归并使
用
优化后完整代码：
#include<iostream>
using namespace std;
void Initialization(int S[],int n){
for(int i=0;i<n;i++)
S[i]=-1;
}
int Find(int S[], int x){
if(S[x] < 0) return x;
else
return S[x] = Find(S,S[x]);
}
void Union(int S[], int Root1, int Root2){
if ( S[Root2] < S[Root1] ) {
S[Root2] += S[Root1];
S[Root1] = Root2;
}
else {
S[Root1] += S[Root2];
S[Root2] = Root1;
}
}
void Input_connection(int S[]){
int u,v;
int Root1,Root2;
cin>>u>>v;
Root1 = Find(S,u-1);
Root2 = Find(S,v-1);
if(Root1 != Root2)
Union (S,Root1,Root2);
}
void Check_connection(int S[]){
int u,v;
int Root1,Root2;
cin>>u>>v;
Root1 = Find(S,u-1);
Root2 = Find(S,v-1);
if(Root1 == Root2)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
void Check_network(int S[],int n){
int i,connect = 0;
for(i=0;i<n;i++){
if(S[i]<0) connect++;
}
if(connect == 1)
cout<<"The network is connected."<<endl;
else
cout<<"There are "<<connect<<" components."<<endl;
}
int main(){
int S[10001];
int n;
char ch;
cin>>n;
Initialization(S,n);
do{
cin>>ch;
switch(ch){
case 'I':Input_connection(S); break;
case 'C':Check_connection(S); break;
case 'S':Check_network(S,n); break;
}
}while(ch != 'S');
return 0;
}