Java | DFS | Clean code
Intuition\n Describe your first thoughts on how to solve this problem. \nAs long as we have at least n-1 cables, we should be able to connect all the n computer
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAs long as we have at least `n-1` cables, we should be able to connect all the `n` computers together. If there are `groups` number of disconnected groups of computers in the networks, the minimum number of cables required to connect all computerse together will be `groups - 1`. Thus, all we need to do is to find the total number of disconnected groups. We can use DFS to identify one group at a time and keep track of the total count.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n+e)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n+e)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n  boolean[] seen;\n  List<Integer>[] adj;\n\n  private void dfs(int node) {\n    seen[node] = true;\n\n    for (var neighbor : adj[node])\n      if (!seen[neighbor])\n        dfs(neighbor);\n  }\n\n  public int makeConnected(int n, int[][] connections) {\n    if (connections.length < n-1) return -1;\n\n    seen = new boolean[n];\n    adj = new ArrayList[n];\n\n    for (var i=0; i<n; i++)\n      adj[i] = new ArrayList<>();\n\n    for (var con : connections) {\n      adj[con[0]].add(con[1]);\n      adj[con[1]].add(con[0]);\n    }\n    var groups = 0;\n\n    for (var i=0; i<n; i++) {\n      if (!seen[i]) {\n        dfs(i);\n        groups++;\n      }\n    }\n    return groups - 1;\n  }\n}\n```\nIf you like my solution, please upvote it!
['Depth-First Search', 'Graph', 'Recursion', 'Java']