并查集

初始化

将每个数字看成一个部落，每个数字的父节点为自身，部落的根节点为首领，即自己为自己部落的首领

int f[N];

for(int i = 1; i <= n; i++) {
    f[i] = i;
}

FindHead操作 (查找部落首领)

当一个数字的父节点是自己的时候，说明自己就是“首领”, 直接返回；否则，就递归查询父节点的父节点。

查询过程中，若层数过多，每次查询都要一层层向上查找，比较费时间，可以进行路径压缩，使得一个节点的父节点即为该节点的“首领”。这样，下次最多只需经过一次向上查询就能找出某个数的“首领”。

• 路径压缩前

• 路径压缩后

int find(int n)
{
    if(f[n] == n) {
        return n;
    }else {
        f[n] = find(f[n]); // 路径压缩
        return f[n];
    }
}

Merge操作 (合并两个部落)

让一个“部落首领”跟从另一个“部落首领”

• 合并前

• 合并后

• 合并 + 路径压缩

在合并的时候需要进行FindHead操作来找到“部落首领”，而FindHead操作的时候即可进行路径压缩。

void merge(int a, int b)
{
    f[find(a)] = f[find(b)];
}

Test操作 (查询两个人是否在同一个部落)

判断两个数否在同一个“部落”，只需要看两个数的“首领”是否一致。如果是，则在同一个“部落”，反之则不在。

• 例: 在下图中

  • 1, 2, 3, 4的“首领”都为3，所以它们是在一个“部落”
  • 5, 6, 7的“首领”都为7，所以它们在同一个“部落”
  • 2的“首领”是3，6的“首领”是7，所以它们不在同一“部落”

bool test(int a, int b)
{
    return find(a) == find(b);
}