Number of Operations to Make Network Connected

Problem Id: 1319 Difficulty: Medium Tag: Depth-first Search Tag: Breadth-first Search Tag: Union Find


This problem is about the connection of Graph. And the first thing come to my mind is Union Find. Now let's consider how to solve this problem using Union Find.

First thing is that, if a graph with n nodes is connected, then the number of edges must be greater or equal to n - 1, where n - 1 is the number of edges in the spanning tree.

Then we need to consider that, if a graph has 2 connected components, then we could make the graph connected by adding one edge with 2 nodes each from one connected graph.

The last thing is that, for each connected component, if there are additional edges in this component except for the spanning tree, then we could change those edges while keep the component connected.


class DSU:
    def __init__(self, size):
        self.size = size = list(range(size))

    def find(self, p):
        if[p] != p:
  [p] = self.find([p])

    def union(self, p, q):
        rp, rq = self.find(p), self.find(q)
        if rp != rq:
  [rp] = rq

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1
        dsu = DSU(n)
        for p, q in connections:
            dsu.union(p, q)

        groups = set()
        for i in range(n):
        return len(groups) - 1