2023.03.23 Today's Challenge

https://leetcode.com/problems/number-of-operations-to-make-network-connected/

Number of Operations to Make Network Connected - LeetCode

오늘은 DFS로 푸는 문제!

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1

        g = [set() for i in range(n)]
        for u, v in connections:
            g[u].add(v)
            g[v].add(u)
        
        visited = [0] * n

        def dfs(node):
            if visited[node]:
                return 0
            visited[node] = 1
            for neighbor in g[node]:
                dfs(neighbor)
            return 1
        
        return sum(dfs(node) for node in range(n)) - 1