LC 1319 [M] Number of Operations to Make Network Connected - ALawliet/algorithms GitHub Wiki

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        # we need at least n - 1 edges to connect all nodes (like a tree) else it is not possible
        if len(connections) < n - 1: return -1
        
        visited = set()
 
        G = [[] for _ in range(n)]
        
        count = 0
        for u, v in connections:
            G[u].append(v) ; G[v].append(u)
            
        def dfs(u):
            visited.add(u)

            for v in G[u]:
                if v not in visited:
                    dfs(v)
            
        for u in range(n):
            if u not in visited:
                dfs(u)
                count += 1
                
        # to connect 2 nodes, we set 1 cable so - 1
        return count - 1