给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。
示例 1: 输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]] 0 3 | | 1 --- 2 4 输出: 2 示例 2: 输入: n = 5 和 edges = [[0, 1], [1, 2], [2, 3], [3, 4]] 0 4 | | 1 --- 2 --- 3 输出: 1 注意: 你可以假设在 edges 中不会出现重复的边。 而且由于所以的边都是无向边，[0, 1] 与 [1, 0] 相同，所以它们不会同时在 edges 中出现。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
参考：并查集
class dsu { public: vector<int> f; dsu(int n) { f = vector<int>(n); for(int i = 0; i < n; ++i) f[i] = i; } void merge(int a, int b) { int fa = find(a); int fb = find(b); f[fa] = fb; } int find(int a) { int origin = a; while(a != f[a]) a = f[a]; return f[origin] = a; } int countUni() { int count = 0; for(int i = 0; i < f.size(); ++i) { if(i == find(i)) count++; } return count; } }; class Solution { public: int countComponents(int n, vector<vector<int>>& edges) { dsu u(n); for(auto& e : edges) u.merge(e[0],e[1]); return u.countUni(); } };32 ms 10.9 MB
我的博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
