Graphs(Union Find): 547. Number of Provinces

547. Number of Provinces

 

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        # dfs 로..

        # init
        n = len(isConnected)
        province = 0
        visited = [False]*n

        def dfs(cur_node_number: int):
            visited[cur_node_number] = True
            for neighbor in range(n):
                if isConnected[cur_node_number][neighbor] == 1 and visited[neighbor] == False:
                	# visited[neighbor] = True <- dfs 들어가면 바로 True 로 바뀔꺼니, 여기서는 생략
                    dfs(neighbor)

        for i in range(n):
            if visited[i] == False: # 방문 안한 노드들
                dfs(i)
                province +=1

        return province

 

https://youtu.be/UgBcBFRatDU?si=7U1S3m6mjFQT2rOk

 

 

Union Find

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        # 도시(노드)의 개수 (Number of cities (nodes))
        n = len(isConnected)

        # 초기 부모 배열 (Initialize the parent array)
        # 각 노드는 처음에 자기 자신을 부모로 설정함 (Each node is its own parent initially)
        par = [i for i in range(n)]

        # 초기 랭크 배열 (Initialize the rank array)
        # 모든 노드의 트리 높이를 1로 초기화 (Start with rank 1 for all nodes)
        rank = [1] * n

        # 부모(루트 노드)를 찾는 함수 (Find function to locate the root parent)
        def findPar(node):
            res = node  # 현재 노드를 시작으로 (Start with the current node)

            # 루트 노드를 찾을 때까지 반복 (Keep moving up until the root parent is found)
            while res != par[res]:
                par[res] = par[par[res]]  # 경로 압축으로 부모를 루트로 설정 (Path compression to make the parent point to the root)
                res = par[res]  # 부모로 이동 (Move to the parent)
            return res  # 루트 부모 반환 (Return the root parent)

        # 두 노드를 같은 그룹으로 합치는 함수 (Union function to merge two nodes into the same group)
        def union(n1, n2):
            # 두 노드의 루트 부모를 찾음 (Find the root parents of both nodes)
            p1, p2 = findPar(n1), findPar(n2)

            # 이미 같은 그룹이라면 아무 작업도 하지 않음 (If they are already in the same group, do nothing)
            if p1 == p2:
                return 0

            # 랭크 기반으로 트리를 합침 (Union by rank to keep the tree balanced)
            if rank[p1] > rank[p2]:  # p1의 트리가 더 높으면 (If p1's tree is taller)
                par[p2] = p1  # p2의 부모를 p1로 설정 (Make p1 the parent of p2)
                rank[p1] += rank[p2]  # p1의 랭크를 갱신 (Update the rank of p1)
            else:  # p2의 트리가 더 높거나 같으면 (If p2's tree is taller or equal)
                par[p1] = p2  # p1의 부모를 p2로 설정 (Make p2 the parent of p1)
                rank[p2] += rank[p1]  # p2의 랭크를 갱신 (Update the rank of p2)

            return 1  # 그룹이 합쳐졌으므로 1 반환 (Return 1 as a union occurred)

        # 연결 요소(프로빈스) 개수를 초기화 (Initialize the count of connected components (provinces))
        count = n

        # 연결 상태를 확인하고 그룹을 합침 (Check connections and perform union operations)
        for n1 in range(n):
            for n2 in range(n):
                if isConnected[n1][n2] == 1:  # 두 도시가 연결되어 있으면 (If two cities are directly connected)
                    count -= union(n1, n2)  # union 결과에 따라 count 감소 (Decrease count based on union result)

        return count  # 최종 연결 요소 개수 반환 (Return the final count of connected components)