题目描述
给定编号从 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 中出现。
算法1
(并查集)
时间复杂度 $O(n)$
C++ 代码
class Solution {
public:
int countcount(int n, vector<vector<int>>& edges) {
p = vector<int>(n, 0);
count = n;
for (int i = 0; i < n; ++i) {
p[i] = i;
}
for (vector<int>& edge : edges) {
uni(edge[0], edge[1]);
}
return count;
}
int find(int a) {
if (a == p[a])
return a;
return p[a] = find(p[a]);
}
void uni(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa == pb)
return;
p[pa] = pb;
count --;
}
private:
vector<int> p;
int count;
};