并查集
并查集是一种树形的数据结构，顾名思义，它用于处理一些不相交集的合并和查询问题。它支持两种操作：
1.查找（Find）：确定某个元素处于哪个集合
2.合并（Union）：将两个子集合并成一个集合
在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
一般我们用一个数组来表示全部集合，数组有两种初始化的方式，第一种，数组每个元素都设置为-1，理由是数组下标都是非负整数，用负数可以标记一个集合的根节点，且-1表示集合有一个元素或者树的高度为1，这可以便于我们实现后面的优化求并法；第二种，将数组的元素设置为对应的下标，即S[i] = i，但是这样提供的信息就少了，如果要实现优化求并，就需要另建一个一维数组来表示集合元素的大小或者高度。
对于查找操作，我们很容易通过递归实现：
//第一种初始化方式的Find操作
int Find(int* S, int x){
if(S[x] < 0){
return x;
}
return Find(S, S[x]);
}
//第二种初始化方式的Find操作
int Find(int* S, int x){
if(S[x] == x){
return x;
}
return Find(S, S[x]);
}
合并操作也十分简单，只要找到两个元素的根节点，将其中一个集合接在另一个集合上集合即可：
void Union(int* S, int x1, int x2){
int root1 = Find(S, x1);
int root2 = Find(S, x2);
if(root1 == root2){ //如果已经属于同一集合了，不必再合并了
return;
}
S[root1] = root2; //或者S[root2] = root1;
}
这就是并查集操作的基本实现了，但是这种方式的时间复杂度较高，需要进一步优化，因此对于Find操作，我们可以通过一种叫做路径压缩的方法来优化。实际上就是在递归的过程中将路径上的结点都直接接到根节点上，这样就可以让我们后面的Find操作速度更快，压缩了到根节点的路径。
//路径压缩(第一种初始化)
int Find(int* S, int x){
if(S[x] < 0){
return x;
}
return S[x] = Find(S, S[x]); //递归的过程中将每个结点直接接到根节点
}
//路径压缩(第二种初始化)
int Find(int* S, int x){
if(S[x] == x){
return x;
}
return S[x] = Find(S, S[x]);
}
同样地，对于合并操作我们也可以进行相应的优化。不难想到，我们在进行合并操作的时候，如果一颗高的树接在了矮树下面，就会使新树变高，这样会使得我们在使用Find操作时花费更长的时间，因此我们希望让较矮的树接在高树下面，极可能使树的高度增长的慢些，这种实现方法为按高度求并。
//第一种初始化
void Union(int* S, int x1, int x2){
int root1 = Find(S, x1);
int root2 = Find(S, x2);
if(root1 == root2){
return;
}
if(S[root1] < S[root2]){ //说明树1更高
S[root2] = root1;
}
else if(S[root1] > S[root2]){ //树2更高
S[root1] = root2;
}
else{ //如果两树一样高，选择一个接到另一个下面，然后更新高度
S[root1] = root2;
S[root2]--;
}
}
//第二种初始化
int TreeHight[Size]; //需要一个额外的数组表示高度，且初始化为1
void Union(int* S, int x1, int x2){
int root1 = Find(S, x1);
int root2 = Find(S, x2);
if(root1 == root2){
return;
}
if(TreeHight[root1] > TreeHight[root2]){
S[root2] = root1;
}
else if(TreeHight[root1] < TreeHight[root2]){
S[root1] = root2;
}
else{
S[root1] = root2;
TreeHight[root2]++;
}
}
另一种实现方法为按大小求并，即根据集合元素的数量大小合并，使得总让较小的树成为较大的树的子树。
//方法一的初始化(此时-1，表示集合元素数为1)
void Union(int* S, int x1, int x2){
int root1 = Find(S, x1);
int root2 = Find(S, x2);
if(root1 == root2){
return;
}
if(S[root1] < S[root2]){
S[root2] = root1;
S[root1]--;
}
else if(S[root1] > S[root2]){
S[root1] = root2;
S[root2]--;
}
else{
S[root1] = root2;
S[root2]--;
}
}
//方法二的初始化
int TreeSize[Size]; //初始化为1
void Union(int* S, int x1, int x2){
int root1 = Find(S, x1);
int root2 = Find(S, x2);
if(root1 == root2){
return;
}
if(TreeSize[root1] > TreeSize[root2]){
S[root2] = root1;
TreeSize[root1]++;
}
else if(TreeSize[root1] < TreeSize[root2]){
S[root1] = root2;
TreeSize[root2]++;
}
else{
S[root1] = root2;
TreeSize[root2]++;
}
}
一般来说我们会同时使用Find和Union操作的优化方法，但是单独使用的效果同样也是不错的。我个人比较倾向于使用方法一的方式初始化。
相关例题：
LeetCode 684.冗余连接
代码如下：
//路径压缩
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[root1] < S[root2])
S[root2] = root1;
else if(S[root1] > S[root2]){
S[root1] = root2;
S[root2]--;
}
else{
S[root1] = root2;
S[root2]--;
}
}
int* findRedundantConnection(int** edges, int edgesSize, int* edgesColSize, int* returnSize){
*returnSize = 2;
int* res = (int*)calloc(2, sizeof(int));
int* S = (int*)calloc(edgesSize + 1, sizeof(int));
for(int i = 0; i < edgesSize; i++){
int root1 = Find(S, edges[i][0]);
int root2 = Find(S, edges[i][1]);
if(root1 == root2){
res[0] = edges[i][0];
res[1] = edges[i][1];
}
else Union(S, root1, root2);
}
free(S);
return res;
}
有时候，如果集合的元素是字符串的话，我们就需要加一个哈希表来表示，字符串映射到S数组上的下标。下题我使用的uthash.h库文件封装好的哈希表，具体操作可以自己去了解一下。
例题：
LeetCode 面试题17.07.婴儿名字
代码如下：
#define MaxSize 40
struct SetType{
char* name;
int size; //名字的大小
};
typedef struct SetType SetType;
struct my_struct{
char* name;
int pos; //此名在集合数组中的下标
UT_hash_handle hh;
};
int Find(int* S, int x){ //路径压缩
if(S[x] < 0)
return x;
else
return S[x] = Find(S, S[x]);
}
void Union(int* S, SetType* T, int root1, int root2){
if(strcmp(T[root1].name, T[root2].name) < 0){ //判断字典序
S[root1] += S[root2];
S[root2] = root1;
}
else{
S[root2] += S[root1];
S[root1] = root2;
}
}
char** trulyMostPopular(char** names, int namesSize, char** synonyms, int synonymsSize, int* returnSize){
struct my_struct *s = NULL, *users = NULL;
*returnSize = 0;
char** res = (char**)calloc(namesSize, sizeof(char*));
SetType* T = (SetType*)calloc(namesSize, sizeof(SetType));
int* S = (int*)calloc(namesSize, sizeof(int));
int empty = 0; //空闲位置
for(int i = 0; i < namesSize; i++){
char* tmp = names[i];
int count = 0; //出现频率
int l = 0;
while(tmp[l] != '(')
l++;
int r = l + 1;
while(tmp[r] != ')'){
count = count * 10 + tmp[r] - '0';
r++;
}
tmp[l] = '\0';
s = (struct my_struct *)malloc(sizeof(struct my_struct));
s->name = names[i];
s->pos = empty;
HASH_ADD_STR(users, name, s);
T[empty].name = names[i];
T[empty].size = l;
S[empty] = -count;
empty++;
}
struct my_struct *p = NULL;
for(int i = 0; i < synonymsSize; i++){
char* tmp = synonyms[i];
char *left, *right;
int l = 1;
while(tmp[l] != ',') l++;
int r = l;
while(tmp[r] != ')') r++;
left = &(tmp[1]);
right = &(tmp[l + 1]);
tmp[l] = tmp[r] = '\0';
HASH_FIND_STR(users, left, p);
if(!p) continue;
int root1 = Find(S, p->pos);
HASH_FIND_STR(users, right, p);
if(!p) continue;
int root2 = Find(S, p->pos);
if(root1 == root2) continue; //这里的判断特别重要，如果已经是同一个父亲了就不要合并了
Union(S, T, root1, root2);
}
for(int i = 0; i < empty; i++){
if(S[i] < 0){
res[(*returnSize)] = (char*)calloc(MaxSize, sizeof(char));
sprintf(res[(*returnSize)], "%s(%d)", T[i].name, -S[i]);
(*returnSize)++;
}
}
free(S);
free(T);
//HASH_CLEAR(hh, users); //不用全局变量的话其实不清除也可以，不然很花时间
return res;
}