给定编号从 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——朴素并查集:
# 初始化,p存储每个点的父节点
p = list(range(n))
# 返回x的祖宗节点
def find(x):
if p[x] != x:
# 路径压缩
p[x] = find(p[x])
return p[x]
# 合并a和b所在的两个集合
p[find(a)] = find(b)
模板 2——维护 size 的并查集:
# 初始化,p存储每个点的父节点,size只有当节点是祖宗节点时才有意义,表示祖宗节点所在集合中,点的数量
p = list(range(n))
size = [1] * n
# 返回x的祖宗节点
def find(x):
if p[x] != x:
# 路径压缩
p[x] = find(p[x])
return p[x]
# 合并a和b所在的两个集合
if find(a) != find(b):
size[find(b)] += size[find(a)]
p[find(a)] = find(b)
模板 3——维护到祖宗节点距离的并查集:
# 初始化,p存储每个点的父节点,d[x]存储x到p[x]的距离
p = list(range(n))
d = [0] * n
# 返回x的祖宗节点
def find(x):
if p[x] != x:
t = find(p[x])
d[x] += d[p[x]]
p[x] = t
return p[x]
# 合并a和b所在的两个集合
p[find(a)] = find(b)
d[find(a)] = distance
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
p = list(range(n))
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
for a, b in edges:
p[find(b)] = find(a)
return sum(i == find(i) for i in range(n))
class Solution {
private int[] p;
public int countComponents(int n, int[][] edges) {
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
for (int[] e : edges) {
int a = e[0], b = e[1];
p[find(b)] = find(a);
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (i == find(i)) {
++cnt;
}
}
return cnt;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
class Solution {
public:
vector<int> p;
int countComponents(int n, vector<vector<int>> &edges) {
p.resize(n);
for (int i = 0; i < n; ++i)
{
p[i] = i;
}
for (auto e : edges)
{
int a = e[0], b = e[1];
p[find(b)] = find(a);
}
int cnt = 0;
for (int i = 0; i < n; ++i)
{
if (i == find(i))
++cnt;
}
return cnt;
}
int find(int x) {
if (p[x] != x)
{
p[x] = find(p[x]);
}
return p[x];
}
};
var p []int
func countComponents(n int, edges [][]int) int {
p = make([]int, n)
for i := 1; i < n; i++ {
p[i] = i
}
for _, e := range edges {
a, b := e[0], e[1]
p[find(b)] = find(a)
}
cnt := 0
for i := 0; i < n; i++ {
if i == find(i) {
cnt++
}
}
return cnt
}
func find(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}