Leetcode 2348. Number of Operations to Make Network Connected with Python

문제

There are n computers numbered from 0 to n - 1 connected by ethernet cables connections 
forming a network where connections[i] = [ai, bi] 
represents a connection between computers ai and bi. Any computer can reach any other computer 
directly or indirectly through the network.

You are given an initial computer network connections. 
You can extract certain cables between two directly connected computers, 
and place them between any pair of disconnected computers to make them directly connected.

Return the minimum number of times you need to do this in order to make all the computers connected. 
If it is not possible, return -1.

0~n-1까지의 번호가 붙은 n개의 컴퓨터가 [$a_i, b_i$] 네트워크 쌍으로 연결되어 있다.
초기 네트워크의 상태가 주어졌을때, 당신은 특정 연결쌍을 끊고 다른 연결쌍을 생성할수 있습니다.
모든 컴퓨터가 상호간 연결되도록 하기 위해 몇번이나 연결쌍을 교체해야 할까요?
만약 불가능하다면 -1을 리턴하세요.

예시

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: 1-2 연결된 케이블을 뽑고 1-3에 연결하면 된다.

제한

• $1 <= n <= 10^5$
• $1 <= connections.length <= min(n * (n - 1) / 2, 10^5)$
• $connections[i].length == 2$
• $0 <= a_i, b_i < n$
• $a_i != b_i$
• 반복되는 연결은 없다.
• 두 컴퓨터에 한개를 초과하는 연결이 이루어지진 않는다.

풀이법

• 겉보기엔 어려워 보이지만, 사실상 전체 그래프를 이루는 연결된 그래프의 갯수를 구하는 문제이다.
• 연결되지 않은 그래프 n개에 대해 n-1번의 재연결을 통해 서로 연결이 가능하기에
• 연결된 그래프 갯수 - 1 을 리턴하면 된다.
• 연결된 그래프의 갯수를 구하기 위해선 DFS를 사용했다. BFS로도 가능하다.

from typing import List, Set

class Node:
    def __init__(self):
        self.to = set()
    def addLine(self, i):
        self.to.add(i)

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if n - 1 > len(connections): return -1
        
        graph = [Node() for _ in range(n)]
        for con in connections:
            graph[con[0]].addLine(con[1])
            graph[con[1]].addLine(con[0])
            
        check = [0] * n
        
        def dfs(x: int):
            check[x] = 1
            for next in graph[x].to:
                if not check[next]:
                    dfs(next)
                    
        island = 0
        for computer in range(n):
            if not check[computer]:
                dfs(computer)
                island += 1

        return island - 1