[LeetCode] 1319. Number of Operations to Make Network Connected

- Problem

1319. Number of Operations to Make Network Connected

- DFS 풀이

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        def dfs(cur):
            for nei in graph[cur]:
                if nei not in visited:
                    visited.add(nei)
                    dfs(nei)

        if len(connections) < n - 1:
            return -1

        graph = defaultdict(list)

        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)
        
        visited = set()
        answer = 0

        for i in range(n):
            if i not in visited:
                dfs(i)
                answer += 1
        
        return answer - 1

- BFS 풀이

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        def bfs(cur):
            q = deque([cur])
            visited.add(cur)

            while q:
                x = q.popleft()
                for nei in graph[x]:
                    if nei not in visited:
                        visited.add(nei)
                        q.append(nei)
        
        if len(connections) < n - 1:
            return -1

        graph = defaultdict(list)
        visited = set()
        answer = 0

        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)
        
        for i in range(n):
            if i not in visited:
                bfs(i)
                answer += 1
        
        return answer - 1

- Union-find 풀이

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        def find(x):
            if x != parent[x]:
                parent[x] = find(parent[x])
            return parent[x]

        if len(connections) < n - 1:
            return -1

        parent = [i for i in range(n)]
        seperated_computers = n

        for u, v in connections:
            x, y = find(u), find(v)
            if x != y:
                parent[x] = y
                seperated_computers -= 1
        
        return seperated_computers - 1

- 결과