323_无向图中连通分量的数目

类型：图

无向图中连通分量的数目 💛

https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph/

❓ 给你一个无向图，包含 n 个结点，其中结点编号从 0 ~ n-1，边则以边集数组的形式存储。

请你计算图中连通分量的数目。

输入: n = 5 和 edges = 0, 1

 0          3
 |          |
 1 --- 2    4

输出: 2

💡 并查集 - 普通

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.cnt = n

    def find(self, x):
        while x != self.parent[x]:
            x = self.parent[x]
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        self.parent[root_x] = root_y
        self.cnt -= 1

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind(n)
        for x, y in edges:
            uf.union(x, y)
        return uf.cnt

💡 并查集 + 路径压缩

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.cnt = n

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        self.parent[root_x] = root_y
        self.cnt -= 1

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind(n)
        for x, y in edges:
            uf.union(x, y)
        return uf.cnt

💡 并查集 + 路径压缩 + 按秩合并

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.cnt = n

    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] > self.rank[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] = root_y
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_y] += 1 
        self.cnt -= 1

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind(n)
        for x, y in edges:
            uf.union(x, y)
        return uf.cnt