# Leetcode 547. Number of Provinces

## DFS

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        length = len(isConnected)
        visited = [False for i in range(length)] # 是否被訪問
        output = 0

        for node in range(length):
            if visited[node]: # 已訪問過就不訪問
                continue
            else:
                # DFS
                stack = [node]
                while stack:
                    current = stack.pop()
                    neighbors = isConnected[current]
                    for i in range(len(neighbors)): # 訪問所有相鄰節點
                        if current == i or visited[i]:  # 自己或是已經訪問過的節點就跳過
                            continue
                        elif neighbors[i] == 1:  # 相鄰節點入棧，標記已訪問
                            stack.append(i)
                            visited[i] = True
                visited[node] = True # 標記自己已訪問
                output += 1  # 省份加一
        return output

## Union Find

class UnionFindSet:
    def __init__(self, size: int):
        self.parent = [i for i in range(size + 1)]
        self.ranks = [0 for i in range(size + 1)]
    
    def find(self, x: int) -> int:
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, u: int, v: int) -> bool:
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        
        if self.ranks[pu] > self.ranks[pv]:
            self.parent[pv] = pu
        elif self.ranks[pu] > self.ranks[pv]:
            self.parent[pv] = pu
        else:
            self.parent[pu] = pv
            self.ranks[pu] += 1
        return True

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        size = len(isConnected)
        uf = UnionFindSet(size)
        for i in range(size):
            for j in range(i+1, size):
                if isConnected[i][j] == 1:
                    uf.union(i,j)
        res = set()
        for i in range(size):
            res.add(uf.find(i))
        return len(res)