1319. Number of Operations to Make Network Connected

Intuition

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.

Solution

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):
            groups.add(dsu.find(i))
        return len(groups) - 1

Information

  • Created: 2020-01-12 16:19:04

  • Last Motified: 2020-01-12 16:19:04

  • Tags: Depth-first Search, Breadth-first Search, Union Find