亲宝软件园·资讯

展开

[leetcode] 并查集(Ⅰ)

sinkinben 人气:2
## 预备知识 并查集 (Union Set) 一种常见的应用是计算一个图中连通分量的个数。比如: ```text a e / \ | b c f | | d g ``` 上图的连通分量的个数为 2 。 并查集的主要思想是在每个连通分量的集合中,选取一个代表,作为这个连通分量的根。根的选取是任意的,因为连通分量集合中每个元素都是等价的。我们只需关心根的个数(也是连通分量的个数)。例如: ``` text a e / | \ / \ b c d f g ``` 也就是说:`root[b] = root[c] = root[d] = a` 而 `root[a] = -1`(根节点的特征也可以定义为 `root[x] = x`)。 最后计算 `root[x] == -1` 的个数即可,这也就是连通分量的个数。伪代码如下: ```cpp // n nodes, all nodes is independent at the beginning vector 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` 函数也可以通过迭代实现: ```cpp 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; } ``` ## 朋友圈 题目[547]:点击 [

加载全部内容

相关教程
猜你喜欢
用户评论