1319. Number of Operations to Make Network Connected

Link

Solution

用DFS找出有幾個connected group若, group 數 -1 即為要花多少cable去補救。

• Time: O(n+m), m is the length of connections

• Space: O(n)

  public int makeConnected(int n, int[][] connections) {
        if(n-1 > connections.length) return -1;
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        
        for(int[] connection : connections){
           graph[connection[0]].add(connection[1]);
           graph[connection[1]].add(connection[0]);
        }
        
        int components = 0;
        int[] node = new int[n];
        for(int k = 0; k < n; k++){
            components += dfs(graph, node, k);
        }
        return components - 1;
    }
    
    public int dfs( List<Integer>[] graph, int[] node, int index){
        if(node[index] == 1) return 0; 
        node[index] = 1;
        
        for(int adj : graph[index]) dfs(graph, node, adj);
        return 1;
    }