1319. Number of Operations to Make Network Connected

 一刷 07/2022

Version #1 DFS

We just need to count the number of connected components

Time O(N) - N is number of nodes

Space O(E) - number of edges

Runtime: 45 ms, faster than 19.38% of Java online submissions for Number of Operations to Make Network Connected.

Memory Usage: 74.6 MB, less than 31.76% of Java online submissions for Number of Operations to Make Network Connected.

class Solution {

    public int makeConnected(int n, int[][] connections) {

        // If we have more than n - 1 cables then we are able to connect all the computers

        if (connections.length < n - 1) {

            return -1;

        }

        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {

            graph.add(new ArrayList<>());

        }

        for (int[] conn : connections) {

            graph.get(conn[0]).add(conn[1]);

            graph.get(conn[1]).add(conn[0]);

        }

        int componentCnt = 0;

        Set<Integer> visited = new HashSet<>();

        for (int i = 0; i < n; i++) {

            if (visited.add(i)) {

                dfs(i, graph, visited);

                componentCnt++;

            }

        }

        return componentCnt - 1;

    }

    

    private void dfs(int i, List<List<Integer>> graph, Set<Integer> visited) {

        for (int next : graph.get(i)) {

            if (visited.add(next)) {

                dfs(next, graph, visited);

            }

        }

    }

}