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