[leetcode] 并查集（Ⅰ）
预备知识
并查集 (Union Set) 一种常见的应用是计算一个图中连通分量的个数。比如：
a e
/ \ |
b c f
| |
d g
上图的连通分量的个数为 2 。
并查集的主要思想是在每个连通分量的集合中，选取一个代表，作为这个连通分量的根。根的选取是任意的，因为连通分量集合中每个元素都是等价的。我们只需关心根的个数（也是连通分量的个数）。例如：
a e
/ | \ / \
b c d f g
也就是说：root[b] = root[c] = root[d] = a 而 root[a] = -1（根节点的特征也可以定义为 root[x] = x）。
最后计算 root[x] == -1 的个数即可，这也就是连通分量的个数。伪代码如下：
// n nodes, all nodes is independent at the beginning
vector<int> root(n, -1);
int find(int x)
{
return root[x] == -1 ? x : (root[x] = find(root[x]));
}
// if x and y are connected, then call union(x, y)
void unionSet(int x, int y)
{
x = find(x), y = find(y);
if (x != y) root[x] = y; // it also can be root[y] = x
}
int main()
{
// (x,y) are connected
while (cin >> x >> y)
unionSet(x, y);
// print the number of connectivity components
print(count(root.begin(), root.end(), -1));
}
find 函数也可以通过迭代实现：
int find(int x)
{
int t = -1, p = x;
while (root[p] != -1) p = root[p];
while (x != p) {t = root[x]; root[x] = p; x = t;}
return p;
}
朋友圈
版权声明：本文为sinkinben原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。