23.03.23 Today’s Leetcode

1319. Number of Operations to Make Network Connected (medium)

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        tree = defaultdict(list)
        for a, b in connections:
            tree[a].append(b)
            tree[b].append(a)
        
        visited = [False] * n
        count = 0
        def dfs(cur, prev):
            if visited[cur]:
                return
            visited[cur] = True
            for node in tree[cur]:
                if node != cur:
                    dfs(node, cur)
    
        for i in range(n):
            if not visited[i]:
                count += 1
                dfs(i, -1)
        
        if len(connections) >= n - 1:
            return count - 1
        return -1