Connected components in undirected graph
Minimum edges to make n nodes connected is n - 1.\n\nCount of existing connected components - 1 is minimum edges to add make the whole graph connected.\n\nTo fi
Minimum edges to make n nodes connected is n - 1.\n\nCount of existing connected components - 1 is minimum edges to add make the whole graph connected.\n\nTo find all the components of a graph, we simply loop through its vertices, and do DFS search on unvisited ones. A search that begins at v will find the entire component containing v (and no more) before returning. \n```\nclass Solution {\n    public int makeConnected(int n, int[][] connections) {\n        if (connections.length < n - 1) {\n            return -1;\n        }\n        \n        List<List<Integer>> adjList = buildGraph(n, connections);\n        \n        boolean[] visited = new boolean[n];\n        int countConnectedComponent = 0;\n        for (int i = 0; i < n; i++) {\n            if (!visited[i]) {\n                dfs(visited, i, adjList);\n                // Detects a connected component\n                countConnectedComponent++;\n            }\n        }\n        \n        return countConnectedComponent - 1;\n    }\n    \n    private  List<List<Integer>> buildGraph(int n, int[][] connections) {\n        List<List<Integer>> adjList = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            adjList.add(new ArrayList<>());\n        }\n        for (int[] connection: connections) {\n            adjList.get(connection[0]).add(connection[1]);\n            adjList.get(connection[1]).add(connection[0]);\n        }\n        return adjList;\n    }\n    \n    private void dfs(boolean[] visited, int from, List<List<Integer>> adjList) {\n        visited[from] = true;\n        for (int to : adjList.get(from)) {\n            if (!visited[to]) {\n                dfs(visited, to, adjList);\n            }\n        }\n    }\n}\n```
[]