File Transfer(并查集）

题目大意：将多个电脑通过网线连接起来，不断查询2台电脑之间是否连通。

问题来源：中国大学mooc

05-树8 File Transfer （25 分）

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

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

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 kcomponents." where k is the number of connected components in this network.

Sample Input 1:

Sample Output 1:

no
no
yes
There are 2 components.

Sample Input 2:

Sample Output 2:

no
no
yes
yes
The network is connected.

思路：并查集的题目，首先知道如何表示并查集的数据结构：

typedef struct{

int data;

int parent;

}SetType[MaxSize];

本题可以进行优化：只用一个数组 int SetType[MaxSize]表示即可，数组下标表示计算机的序号，SetType[index]表示为他的父节点，就是连通节点的序号。

并查集的Find 和union函数如下：

int Find(SetType S[],int x){
  int i;
  for(i=0;i<MaxSize&&S[i].data!=x;i++);     //查找的时间复杂度n
  if(i>MaxSize)return -1;
  for(;S[i].parent>=0;i=S[i].parent);
  return i;   //找到X所属集合，返回树根结点在数组S中的下标
}

void Union(SetType S[],int x1,int x2){
  int root1,root2;
  root1=find(S,x1);
  root2=find(S,x2);
  if(root1!=root2)S[root2]=root1;
  
}

优化后的Find和路径压缩函数如下：

#define Maxitem 10000

int S[Maxitem];
//采用路径压缩，尾递归寻找他的根结点
int find(int x){
    if(S[x]<0)return x;
    ////先找到根； 把根变成 X 的父结点； 再返回根。
    else return S[x]=find(S[x]);
}
 //按秩归并，将根结点数量少的树连接到根结点多的树，这里用S[root]表示根结点
 //S[root]为负数，绝对值为节点数
void Union(int root1,int root2){   
    if(S[root1]>S[root2]){
        S[root2]+=S[root1];
        S[root1]=root2;
    }else {
        S[root1]+=S[root2];
        S[root2]=root1;
    }
}

程序框架：

最终代码如下：

#include<cstdio>
#define Maxitem 10000

int S[Maxitem];
//采用路径压缩，尾递归寻找他的根结点
int find(int x){
    if(S[x]<0)return x;
    ////先找到根； 把根变成 X 的父结点； 再返回根。
    else return S[x]=find(S[x]);
}
 //按秩归并，将根结点数量少的树连接到根结点多的树，这里用S[root]表示根结点
 //S[root]为负数，绝对值为节点数
void Union(int root1,int root2){   
    if(S[root1]>S[root2]){
        S[root2]+=S[root1];
        S[root1]=root2;
    }else {
        S[root1]+=S[root2];
        S[root2]=root1;
    }
}
void initialzation(int n){
    for(int i=0;i<n;i++){
        S[i]=-1;
    }
}
void Input_connection(){
    int u,v,root1,root2;
    scanf("%d %d",&u,&v);
    getchar();
    root1=find(u-1);
    root2=find(v-1);
    Union(root1,root2);
}
void Check_connection(){
    int u,v,root1,root2;
    scanf("%d %d",&u,&v);
    getchar();
    root1=find(u-1);
    root2=find(v-1);
    if(root1==root2)printf("yes
");
    else printf("no
");
}
void Check_networks(int n){
    int count=0;
    for(int i=0;i<n;i++)
    if(S[i]<0)count++;
    if(count==1)printf("The network is connected.
");
    else printf("There are %d components.
",count);
}
int main(){
    char in;
    int n;
    scanf("%d",&n);
    initialzation(n);
    do{
        scanf("%c",&in);
        switch(in){
            case'I':Input_connection();break;
            case'C':Check_connection();break;
            case'S':Check_networks(n);break;
        }
    }while(in!='S');
    return 0;
}