并查集

1.并查集问题中集合存储如何实现？

可以用树结构表示集合，每个节点代表一个集合元素

采用数组形式存储

负数表示根结点；非负数表示双亲结点的下标。

数组中每个元素的类型描述为：

typedef struct {
    ElementType Data;
    int Parent;//相当于指针，表示这个节点的父节点在集合中的位置
} SetType;

2 .集合运算

(1）查找某个元素所在的集合（用根结点表示)

int Find(SetType S[], ElementType X)
{   //在数组S中查找值为X的元素所属的集合
    //Maxsize是全局变量，为数组S的最大长度
    int i;
    for (i=0 ; i < Maxsize && S[i].Data != X; i++);  //当S[i].Data = X时，循环结束，i为X的位置下标
    if(i >= Maxsize)  return -1;  //未找到X，返回-1 则i为根节点的下标
    for (; S[i].Parent >= 0; i = S[i].Parent);  //如果i < Maxsize,寻找父结点，直到S[i].Parent < 0为止（根结点的Parent为-1）
    return i;  //找到X所属集合，返回树根结点在数组S中的下标
}

(2）集合的并运算
①分别找到X1和X2两个元素所在集合树的根结点；
② 如果它们不同根，则将其中一个根结点的父结点指针设置成另一个根结点的数组下标。

void Union(SetType S[ ], ElementType X1, ElementType X2)
{
    int Root1, Root2;
    Root1 = Find(S, X1);
    Root2 = ind(S, X2);
    if (Root1 != Root2)  //当x1和x2不属于同一子集时，才需要合并
       S[Root2].Parent = Root1;  
}

为了改善合并以后的查找性能，可以采用小的集合合并到相对大的集合中。(修改Union函数)

void Union(SetType S, SetName Root1, SetName Root2)
{   //这里默认Root1和Root2是不同集合的根结点
    //保证小集合并入大集合
    if ( S[Root2] < S[Root1] ) {  //如果集合2比较大
        S[Root2] += S[Root1];     //集合1并入集合2
        S[Root1] = Root2;
    }
    else {                         //如果集合1比较大
        S[Root1] += S[Root2];     //集合2并入集合1
        S[Root2] = Root1;
    }
}

3. 并查集的实现

数组存储形式实现并查集的代码如下所示。

#include<iostream>
using namespace std;
#define MaxSize 1000
typedef int ElementType;
typedef struct {
	ElementType Data; // 存值
	int Parent;  // 指向父结点 
}SetType;

// 查找 
int Find(SetType S[], ElementType X) 
{
	int i;
	for (i = 0; i < MaxSize && S[i].Data != X; i++);  // 找到数组中该值对应的下标 
	if (MaxSize <= i) // 如果没有找到，返回 -1 
		return -1;
	for (; S[i].Parent >= 0; i = S[i].Parent); 	// 找到该结点的根结点 
	return i; // 返回根结点在数组S中的下标 
}

// 并 
void Union(SetType S[], ElementType X1, ElementType X2) 
{
	int root1 = Find(S, X1);  // 找到 X1 的根结点下标 
	int root2 = Find(S, X2);  // 找到 X2 的根结点下标 
	// 如果根结点的下标不同，说明不是一个集合
	if (root1 != root2) 
	{
		S[root1].Parent = root2;   // 把X1挂到X2的集合 
	}
}

int main() 
{
	SetType S[MaxSize];
	// 初始化数组，父结点全部指向-1 
	for (int i = 0; i < MaxSize; i++) 
	{
		S[i].Data = i + 1;
		S[i].Parent = -1;
	}
	cout << Find(S, 5) << endl;
	Union(S, 3, 5);
	cout << Find(S, 4) << endl;
	cout << Find(S, 3) << endl;
	Union(S, 1, 3);
	Union(S, 2, 4);
	Union(S, 8, 6);
	cout << Find(S, 6) << endl;
	cout << Find(S, 8) << endl;
	system("pause");
	return 0;
}

代码运行结果如下图所示。

4.集合的优化

为什么要优化？

问题中每查找一次都要遍历n个节点，若想把所有元素都遍历一遍则时间复杂度为O（n^2）。效率低，故需要进行优化。

优化方案

任何有限集合的N个元素都能映射为0~N-1.故可以大小为N的数组的下标来表示集合元素的位置，数组中存放的值则为其父节点的位置。

代码实现

1.并查集的表示形式

#define MaxSize 100
typedef int ElementType;
typedef int SetName;
typedef ElementType SetType[MaxSize];

2.查找和合并操作

SetName Find(SetType S, ElementType X) {//查找某个元素的根节点
	for (; S[X] >= 0; X = S[X]) {
		//默认集合元素全部初始化为-1
		return X;
	}
}

void Union(SetType S, SetName Root1, SetName Root2) {
	//这里root1和root2是不同节点的根节点
	S[Root2] = S[Root1];
}

例题

输入连接的计算机的数量n，分别编号为1，2，3···n，然后输入要进行的操作。

C表示Check两台计算机是否链接，若链接则输出“Yes”否则输出“No”

I表示Inter即连接两台计算机。

S表示操作结束，退出。

最后判断有几个连接网。（即有计算机相互连通的net有几个，若某个计算机没有和别的计算机联通，则按照它与自己连通来看，也算作一个net）

输入样例：

输出样例：

程序框架搭建：

int main() {
	SetType S;
	int n;
	char in;
	scanf("%d", &n);
	Initialization(S, &n);//建立一个容量为n的集合
	do {
		scanf("%c", &in);
		switch (in) {
		case 'I':Input_connection(S); break;//建立连接
		case 'C':Check_connection(S); break;//检查是否连接
		case 'S':Check_network(S, n); break;//检查有几个net
		}
	} while (in != 'S');
	return 0;
}

方法实现

SetName Find(SetType S, ElementType X) {//查找某个元素的根节点
	for (; S[X] >= 0; X = S[X]) {
		//默认集合元素全部初始化为-1
		return X;
	}
}


void Union(SetType S, SetName Root1, SetName Root2) {
	//这里root1和root2是不同节点的根节点
	S[Root2] = S[Root1];
}


void Input_connection(SetType S) {
	ElementType u, v;
	SetName Root1, Root2;
	scanf("%d %d\n", &u, &v);
	Root1 = Find(S, u - 1);
	Root2 = Find(S, v - 1);
	if (Root1 != Root2) {
		Union(S, Root1, Root2);
	}
}


void Check_connection(SetType S) {
	ElementType u, v;
	SetName Root1, Root2;
	scanf("%d %d\n", &u, &v);
	Root1 = Find(S, v - 1);//计算机的编号为1，2....n映射到集合上为0，1....n-1.故传入的数据应为u-1
	Root2 = Find(S, v - 10);
	if (Root1 == Root2) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
}


void Check_network(SetType S, int n) {
	int i, counter = 0;
	for (i = 0; i < n; i++) {
		if (S[i] < 0)counter++;
	}
	if (counter == 1) {
		printf("The network is connected.\n");
	}
	else {
		printf("There are %d components.\n", counter);
	}
}

在PTA上的运行结果：

运行超时原因分析：

把高的树插到矮的树上会导致树的高度不断变高，随着集合的不断合并，树高不断增大，因而查找的次数也不断增多，导致超时。

解决方案：按秩归并

方法1：

void Union(SetType S, SetName Root1, SetName Root2) {
	if (S[Root2] < S[Root1]) //S[Root]=-树高
		S[Root1] = Root2;
	else {
		if (S[Root1] == S[Root2]) S[Root1]--;//树高加1
		S[Root2] = Root1;
	}
}

方法2：

void Union(SetType S, SetName Root1, SetName Root2) {
	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]);
}

数据结构-树（集合）

并查集