[Leetcode] 0323. 無向グラフ内の接続コンポーネントの数

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

中くらい

のグラフがあります n ノード。整数が与えられます n 配列 エッジ どこ エッジ[i] = [a _i , b _i ] の間にエッジがあることを示します _AI そして b_私 グラフで。

戻る グラフ内の接続されたコンポーネントの数.

例 1:

入力： n = 5、エッジ = [[0,1],[1,2],[3,4]]
出力： 2

例 2:

入力： n = 5、エッジ = [[0,1],[1,2],[2,3],[3,4]]
出力： 1

制約:

1 <= n <= 2000
1 <= エッジの長さ <= 5000
エッジ[i].length == 2
0 <= a _i <= b _i < n
a _i != b _i
重複エッジはありません。

パイソン

				
					# time complexity: O(V + E * α(n)) is the inverse Ackermann function
# space complexity: O(V)
from typing import List


class UnionFind():
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, node):
        while node != self.parents[node]:
            node = self.parents[node]
        return node

    def uion(self, nodeX, nodeY):
        parentX = self.find(nodeX)
        parentY = self.find(nodeY)

        if parentX == parentY:
            return

        if self.rank[parentX] > self.rank[parentY]:
            self.parents[parentY] = self.parents[parentX]
        elif self.rank[parentX] < self.rank[parentY]:
            self.parents[parentX] = self.parents[parentY]
        else:
            self.parents[parentX] = self.parents[parentY]
            self.rank[parentY] += 1


class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        disjointUnionSet = UnionFind(n)
        for startVertex, endVertex in edges:
            disjointUnionSet.uion(startVertex, endVertex)

        parent = set()
        for i in range(n):
            parent.add(disjointUnionSet.find(i))
        return len(set(parent))


n = 4
edges = [[0, 1], [2, 3], [1, 2]]
print(Solution().countComponents(n, edges))

中くらい

パイソン

関連記事