[C++知识库]并查集，c/c++描述，完整代码

??并查集，是描述了这样一类问题：我们经常需要合并两个集合，或者经常查询某个元素属于哪个集合。频繁进行合并与查询操作，所以叫做并查集。
??问题如下：已知b与d、e与g、a与c、h与i、a与b、e与f、b与c，各自都是亲戚关系。请问：c与d、g与j、h与i是亲戚关系么？
??课本里介绍了并查集，和几个关键函数，但没有给出完整例题与完整代码。参考请教网上资料后，这里也给出了自己的代码，并没有用到递归。但分析思路是一样的。
??几个关键点的处理如下：
??如何存储数据：所有人的数据组成一维数组。数组里每一个人的数据用结构体表示：含有两个成员：int indexRelation，其亲戚在数组里的下表；char name，本人的名字。以区分不同的人。假设没有同名的人。
??如何判断两人是否为亲戚：先由函数createOrFind找到这两个人的在数组里的下表，如果其亲戚是同一个人，则这两人也为亲戚，否则这俩人就不是亲戚。
??如何建立存储所有人的数组：在输入亲戚关系的时候由函数createOrFind完成，如果输入的这个人已经存在于数组，直接返回其在数组里的下标，如果数组里没有包含这个人的信息，则把此人加入数组，再返回此人的数组下标。因为c语言只能建立定长数组。故还需要一个变量记录数组里实际存储人数，即数组实际长度。每输入一对亲戚后，紧接着合并其所在的家族。家族里可以只有一个人，即族长本身。
??如何查找族长：如果一个人的indexRelation成员等于其自身下标，这个人就是族长，其是族里所有人的亲戚。找到几个族长，就是有几个家族。由函数familyNum完成这个思路。
??如何合并家族：两个家族彼此都是亲戚的话，需要进行合并，并选出新的族长，即是别的文章里介绍的树的根。根据两个家族的成员多少，把人少的家族并到人数多的家族，即修改其indexRelation成员的值，存储大家族族长的下标。人少家族和人多家族的成员下标另由中间数组保存。并计算其数组长度，得到各自家族的人数。这个数组是动态变量，随函数unionSet的建立而存在，unionSet执行完毕则中间数组也被回收，不占用内存空间。
??别的地方提到了rank成员，表示家族成员在家族树里的深度。这里没有用到rank，因为已经做到了家族里族长是其他人的直接亲戚，看做家族树的话，树只有两层。族长单独一层，其他亲戚成员在另外同一层。
??各函数功能如下：
??createOrFind：返回每个人在存人数组里的下标，或者建立此人信息后再返回其下标。
??unionSet：合并两个人所在的家族或者称为集合。
??familyNum：统计存在多少家族，或者说统计数组里有几个集合。
??main函数所在源文件代码：

#include<iostream>
using namespace std;
#define MAXSIZE 1000

struct Relation{
	int indexRelation;
	char name;
};

extern int createOrFind(Relation relation[],int & arrayLength,char name);
extern void unionSet(Relation relation[], int& arrayLength,int indexA,int indexB);
extern int familyNum(Relation relation[], int& arrayLength);

int main() {
	Relation relation[MAXSIZE];
	int arrayLength = 0;
	
	int pairNum;
	cout << "input the number of relation pairs : ";
	cin >> pairNum;

	char peopleA, peopleB;
	int indexA, indexB;
	cout << endl;
	for (int i = 1; i <= pairNum; i++) {
		cout << "input the " << i << "th pair relation : ";
		cin >> peopleA >> peopleB;
		indexA = createOrFind(relation,arrayLength,peopleA);
		indexB = createOrFind(relation, arrayLength, peopleB);
		unionSet(relation,arrayLength,indexA,indexB);
	}
	
	cout <<endl<< "how many times you want to query ? ";
	cin >> pairNum;
	for (int i = 1; i <= pairNum; i++) {
		cout << endl;
		cout << "input the " << i << "th pair you want query : ";
		cin >> peopleA >> peopleB;
		indexA = createOrFind(relation, arrayLength, peopleA);
		indexB = createOrFind(relation, arrayLength, peopleB);
		
		if (relation[indexA].indexRelation == relation[indexB].indexRelation)
			cout << "they are relation"<<endl;
		else
			cout << "they are not relation" << endl;
	}

	cout << endl;
	cout <<"there are "<< familyNum(relation, arrayLength)<<" families"<<endl;
	return 0;
}

各函数所在源文件代码：

#include<iostream>
using namespace std;
#define MAXSIZE 1000

struct Relation {
	int indexRelation;
	char name;
};

int createOrFind(Relation relation[], int& arrayLength, char name) {
	for (int i = 0; i < arrayLength; i++)
		if (relation[i].name == name)
			return i;

	relation[arrayLength].indexRelation = arrayLength;
	relation[arrayLength].name = name;
	arrayLength++;
	return arrayLength - 1;
}
void unionSet(Relation relation[], int& arrayLength, int indexA, int indexB) {
	if (relation[indexA].indexRelation == relation[indexB].indexRelation)
		return;

	int indexParentA = relation[indexA].indexRelation;
	int indexParentB = relation[indexB].indexRelation;
	int familyA[MAXSIZE], lengthAFamily = 0, familyB[MAXSIZE], lengthBFamily = 0;
	for (int i = 0; i < arrayLength; i++) {
		if (relation[i].indexRelation == indexParentA) {
			familyA[lengthAFamily] = i;
			lengthAFamily++;
		}
		if (relation[i].indexRelation == indexParentB) {
			familyB[lengthBFamily] = i;
			lengthBFamily++;
		}
	}
	if (lengthAFamily <= lengthBFamily)
		for (int i = 0; i < lengthAFamily; i++)
			relation[familyA[i]].indexRelation = indexParentB;
	else
		for (int i = 0; i < lengthBFamily; i++)
			relation[familyB[i]].indexRelation = indexParentA;
}
int familyNum(Relation relation[], int& arrayLength) {
	int num = 0;
	for (int i = 0; i < arrayLength; i++)
		if (relation[i].indexRelation == i)
			num++;

	return num;
}

测试结果及对应的亲戚关系如下：


我认为能解决问题就可以。跟很多地方提供的代码不一样没有merge，union、find函数，也没有递归。
谢谢阅读。