https://zhuanlan.zhihu.com/p/93647900/
场景：元素的分组管理问题
基本原理：将所有元素分成多个集合，判断两个元素是否在同一个集合，只需要判断他们的根节点是否相同。
#define NUM 200
// 获取并查集的根节点
int findRoot(int* pNList, int k) {
if (pNList[k] != k) {
// 路径压缩 A->B->C->D => A->D B->D C->D 注意是用当前节点的父节点作为下一个迭代，否则会死循环
pNList[k] = findRoot(pNList, pNList[k]);
}
return pNList[k];
}
// 合并根节点
void mergeRoot(int* nList, int* deepList, int x, int y) {
if (x == y) {
return;
}
// 通过比较两棵树的深度，深度小的并入深度大的，降低总深度，提高性能。
if (deepList[x] <= deepList[y]) {
nList[x] = y;
} else {
nList[y] = x;
}
if (deepList[x] == deepList[y]) {
deepList[y]++;
}
}
void circleInit(int* nList, int* deepList) {
int i;
for (i = 0; i < NUM; i++) {
nList[i] = i;
deepList[i] = 1;
}
}
void circleMerge(int* nList, int i, int j, int** isConnected, int* deepList) {
int x = findRoot(nList, i);
int y = findRoot(nList, j);
if (isConnected[x][y] == 1 || isConnected[i][j] == 1) {
mergeRoot(nList, deepList, x, y);
}
}
int circleResult(int* nList, int size) {
int i = 0;
int result = 0;
for (i = 0; i < size; i++) {
if (nList[i] == i) {
result++;
}
}
return result;
}
int findCircleNum(int** isConnected, int isConnectedSize, int* isConnectedColSize){
int nList[NUM] = {0};
int deepList[NUM] = {0};
int i, j;
circleInit(nList, deepList);
for (i = 0; i < isConnectedSize; i++) {
for (j = i + 1; j < isConnectedColSize[i]; j++) {
circleMerge(nList, i, j, isConnected, deepList);
}
}
return circleResult(nList, isConnectedSize);
}