[Leetcode] 0323. 무방향 그래프의 연결 구성 요소 수

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

중간

당신은 그래프를 가지고 있습니다 N 노드가 주어집니다. N 그리고 배열 가장자리 어디 가장자리[i] = [ _ai , _bi ] 사이에 가장자리가 있음을 나타냅니다. _{일체 포함} 그리고 비 _나는 그래프에서.

반품 그래프의 연결된 구성 요소 수.

예시 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].길이 == 2
0 <= a _i <= b _i < n
_나는 != _나는
반복되는 모서리가 없습니다.

파이썬

				
					# 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))

중간

파이썬

관련 기사