Graphs(싸이클확인, Union Find): 323. Number of Connected Components in an Undirected Graph ★★★★★

323. Number of Connected Components in an Undirected Graph

 

내 풀이

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # 그래프를 인접 리스트로 표현 (Represent the graph as an adjacency list)
        hashMap = {i: [] for i in range(n)}  # 각 노드 i를 키로, 빈 리스트를 값으로 초기화 (Initialize each node with an empty list)
        for n1, n2 in edges:  # 간선 정보를 순회하며 그래프를 채움 (Iterate over edges to build the graph)
            hashMap[n1].append(n2)  # 노드 n1에 n2를 연결 (Connect n2 to n1)
            hashMap[n2].append(n1)  # 노드 n2에 n1을 연결 (Connect n1 to n2)

        # 방문한 노드를 추적하기 위한 집합 (Set to track visited nodes)
        visit = set()

        # 깊이 우선 탐색 함수 정의 (Define a DFS function)
        def dfs(node):
            visit.add(node)  # 현재 노드를 방문으로 표시 (Mark the current node as visited)
            for nn in hashMap[node]:  # 현재 노드에 연결된 모든 이웃 노드를 순회 (Iterate over all neighbors of the current node)
                if nn not in visit:  # 방문하지 않은 이웃 노드가 있다면 (If the neighbor is not visited)
                    dfs(nn)  # 재귀적으로 탐색 (Recursively call DFS)

        count = 0  # 연결 요소의 개수를 저장하는 변수 (Variable to store the number of connected components)
        for i in range(n):  # 모든 노드를 순회 (Iterate over all nodes)
            if i not in visit:  # 방문하지 않은 노드에서 시작 (Start from unvisited nodes)
                dfs(i)  # DFS 호출 (Call DFS)
                count += 1  # 연결 요소 개수 증가 (Increment the count of connected components)
        
        return count  # 연결 요소의 개수를 반환 (Return the number of connected components)

 

Union Find ★★★

https://youtu.be/8f1XPm4WOUc?si=YRd50bOVxwCqxfIH

 

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # unio find
        par = [i for i in range(n)] # parent
        rank = [1] * n

        def find(n1): 
            # node n1 we want to find its root parent so far
            res = n1

            while res != par[res]:
                par[res] = par[par[res]]
                res = par[res]
            return res

        def union(n1, n2):
            p1, p2 = find(n1), find(n2)

            if p1 == p2:
                return 0

            if rank[p2] > rank[p1]:
                par[p1] = p2
                rank[p2] += rank[p1]
            else:
                par[p2] = p1
                rank[p1] += rank[p2]
            return 1

        res = n
        for n1, n2 in edges:
            res -= union(n1, n2)
        return res

 

최종 코드

무방향 그래프에서 연결 요소(Connected Components) 의 개수를 찾는 문제

 

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # 무방향 그래프에서 연결된 컴포넌트 수를 세는 문제

        # 1. Union-Find 초기화
        # par[i] = i → 처음에는 자기 자신이 부모
        par = [i for i in range(n + 1)]  # 노드가 0~n-1까지이지만 n+1로 넉넉히 생성
        rank = [0] * (n + 1)             # rank: 트리 깊이 또는 크기 추정값 (초기 0)

        # 2. Find 함수 (경로 압축 포함)
        def find(n):
            p = par[n]  # 현재 노드의 부모

            # 루트 노드가 아닐 경우 계속 위로 따라가며 경로 압축
            while p != par[p]:
                par[p] = par[par[p]]  # 경로 압축: 조상의 조상으로 건너뜀
                p = par[p]
            return p  # 루트 노드 반환

        # 3. Union 함수 (rank 기준)
        # 두 노드를 하나의 집합으로 묶고, 새롭게 연결됐으면 1 반환, 아니면 0
        def union(n1, n2):
            p1, p2 = find(n1), find(n2)  # 두 노드의 루트 찾기

            if p1 == p2:
                return 0  # 이미 같은 집합이면 연결 X

            # rank가 높은 루트 쪽으로 낮은 쪽을 병합
            if rank[p1] > rank[p2]:
                par[p2] = p1
                rank[p1] += rank[p2]
            else:
                par[p1] = p2
                rank[p2] += rank[p1]
            return 1  # 새롭게 연결됐음을 의미

        # 4. 연결 요소 개수 계산
        res = n  # 처음엔 모든 노드가 각각 독립된 컴포넌트 (n개)

        for a, b in edges:       # 모든 간선 순회
            res -= union(a, b)   # 연결되면 컴포넌트 수 -1

        return res  # 최종 연결 요소 개수 반환