前言

刚开始挺懵逼的，甚至以为要图来解决，后来看了何老师的数据结构并查集的相关概念才知道，原来竟然可以这么操作。

题目

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?

输入格式

Each input file contains one test case. For each test case, the first line contains N (2≤N≤10000), 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 betweenc1andc2; or

S

whereS stands for stopping this case.

输出格式

For each C case, print in one line the word "yes" or "no" if it is possible or impossible to transfer files betweenc1andc2, 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.

样例

输入样例1

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S

输出样例1

no
no
yes
There are 2 components.

输入样例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

输出样例2

no
no
yes
yes
The network is connected.

思路

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
在本题中，最开始将所有的未连接的点都视为一个个只有根结点的树，如果如果任意两个不在同一棵树上的点想要连接到一起，就这两棵树给连接到一起，这种操作被称为并集。
想要检查两个结点是否连接（即是否在同一棵树上），只要分别检查他们的根结点是否相同就行了。
这种需要决定了结点的存储结构上要有往父结点的指针。最好使用数组存储，这样合并集合只需要把其中一棵树的根结点的father改向另一棵树的根结点的位置即可。

struct Node{
    int father;
    int data;
}

还有一些优化相关的，详情见下代码。

实现

完整代码

#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;

const int MaxSize = 10001;

int c[MaxSize];

int myFindRoot(int x);
void myConnect(int x, int y);
void myCheck(int x, int y);
void myCheckAll(int n);
void myUnion(int x, int y);			//按秩优化，牛逼啊

int main() {
	int N;
	cin >> N;	
	for (int i = 1; i < N + 1; i++) 			//初始化，每个元素都是单独的一棵树
		c[i] = -1;
	char order;
	cin >> order;
	while (order != ‘S‘) {
		int c1, c2;
		cin >> c1 >> c2;
		if (order == ‘I‘)
			myConnect(c1, c2);
		else if (order == ‘C‘)
			myCheck(c1, c2);
		cin >> order;
	}
	myCheckAll(N);
	return 0;
}

int myFindRoot(int x) {			//压缩路径，直接让这条路径上的每个点都指向根结点了，树高大幅度降低，真牛逼
	if (c[x] < 0)
		return x;
	else
		return c[x] = myFindRoot(c[x]);
}

void myConnect(int x, int y) {
	int root1,  root2;
	root1 = myFindRoot(x);
	root2 = myFindRoot(y);
	if (root1 != root2)						//检查是否已经连接上了
		myUnion(root1, root2);					//并集
}

void myUnion(int x, int y) {
	if (c[x] == c[y]) {
		c[y] = x;
		c[x]--;
	}
	else if (-c[x] > -c[y])		//小树连接到大树上
		c[y] = x;
	else
		c[x] = y;
}

void myCheck(int x, int y) {
	int root1, root2;
	root1 = myFindRoot(x);
	root2 = myFindRoot(y);
	if (root1 != root2)
		cout << "no" << endl;
	else
		cout << "yes" << endl;
}

void myCheckAll(int n) {				//-1的数目就是根结点的数目！不要搞那么多花里胡哨的！
	int counter = 0;
	for (int i = 1; i < n + 1; i++)
		if (c[i] < 0)
			counter++;
	if (counter == 1)
		cout << "The network is connected.";
	else
		cout << "There are " << counter << " components.";
}

存储结构

由于不需要存储额外的data，所以可以把所有数据的存储简化为一个数组，数组的下标就表示该点的位置。注意这里需要声明为全局变量，因为函数需要访问，不然就需要在使用函数的时候传参进去。
至于每个集合，一个集合可以用一棵树来表示。

int c[MaxSize];

检查函数

检查两个结点是否处在一个集合中，只要分别不断通过指向父结点的指针将存储两个集合的树的根结点找到并检查是否为一个根结点集合，如果是同一个根结点，说明他们在同一个集合内。
这里实现的关键方法就是查找根结点，有一个优化的方法就是使用压缩路径的方法，使用递归来查找，这样查过过程结束后，所以经过的路径都被直接指向了根结点。

int myFindRoot(int x) {			//压缩路径，直接让这条路径上的每个点都指向根结点了，树高大幅度降低，真牛逼
	if (c[x] < 0)
		return x;
	else
		return c[x] = myFindRoot(c[x]);
}

void myCheck(int x, int y) {
	int root1, root2;
	root1 = myFindRoot(x);
	root2 = myFindRoot(y);
	if (root1 != root2)
		cout << "no" << endl;
	else
		cout << "yes" << endl;
}

连接

首先检查是否已经在同一个集合内，如果不在同一个集合的时候，通过连接函数将两个结点所在的集合表示的树连接到一起。
连接函数有一个优化的方法是按秩优化，即每次连接的时候，将矮一点的树连接到高一点的树上面，只有当两棵树高度一致的时候才合并并且高度加一。这样能保证合并后的高度是最小的，可以大大加快查找的速度。
这里有个问题就是如果获知每棵树的高度呢，给出的答案是利用根结点的parent，显示根结点是没有父结点的，所以我们可以利用这个数据，来存储每棵树的高度。

void myConnect(int x, int y) {
	int root1,  root2;
	root1 = myFindRoot(x);
	root2 = myFindRoot(y);
	if (root1 != root2)						//检查是否已经连接上了
		myUnion(root1, root2);					//并集
}

void myUnion(int x, int y) {
	if (c[x] == c[y]) {
		c[y] = x;
		c[x]--;
	}
	else if (-c[x] > -c[y])		//小树连接到大树上
		c[y] = x;
	else
		c[x] = y;
}

File Transfer（并查集的相关概念）

原文：https://www.cnblogs.com/Za-Ya-Hoo/p/12738974.html