1319.number-of-operations-to-make-network-connected.md

1319. Number of Operations to Make Network Connected

Traversal

We can count the number of connected components in the graph (for single node which will also one component itself), then return the number of components - 1.

We don't care about the redundant edges, or how to remove them, or how to connect the components, we just need to know the number of components.

[Group 1] [Group 2] [Group 3] [Group 4]
 a b c       i j       x         y
         +1        +2        +3

[Group 1] [Group 2] [Group 3] 
 a b c d    x y z      i j    
         +1        +2        

How can we check if it's impossible to connect? For n nodes, we need at least n - 1 edges to connect all nodes. So if the number of edges is less than n - 1, we can't connect all nodes.

fun makeConnected(n: Int, connections: Array<IntArray>): Int {
    if (connections.size < n - 1) return -1
    val adjSet = buildGraph(n, connections)
    val visited = BooleanArray(n)
    var componentsCount = 0
    for (i in 0 until n) {
        if (visited[i].not()) {
            dfs(adjSet, i, visited)
            componentsCount++
        }
    }
    return componentsCount - 1
}

private fun dfs(graph: Array<HashSet<Int>>, current: Int, visited: BooleanArray) {
    if (visited[current]) return
    visited[current] = true
    graph[current].forEach { adj ->
        dfs(graph, adj, visited)
    }
}

private fun buildGraph(n: Int, connections: Array<IntArray>): Array<HashSet<Int>> {
    val adjSet = Array<HashSet<Int>>(n) { HashSet<Int>() }
    for (c in connections) {
        val a = c[0]
        val b = c[1]
        adjSet[a].add(b)
        adjSet[b].add(a)
    } 
    return adjSet
}