Image Explanation🏆- [Easiest DFS] - C++/Java/Python
Video Solution\nNumber of Operations to Make Network Connected by Aryan Mittal\n\n\n\n# Approach & Intuition\n\n\n\n\n\nAlthough the same problem of finding num
# Video Solution\n`Number of Operations to Make Network Connected by Aryan Mittal`\n![amazon4.png](https://assets.leetcode.com/users/images/aab14c28-39f6-4861-9bc5-bcfb63e395cb_1679539145.628633.png)\n\n\n# Approach & Intuition\n![image.png](https://assets.leetcode.com/users/images/c23955a7-f24c-4973-ba46-a6aa86e11158_1679534811.488079.png)\n![image.png](https://assets.leetcode.com/users/images/7c7503b9-55d8-4536-a03d-9e578748a8f3_1679534861.280428.png)\n![image.png](https://assets.leetcode.com/users/images/b6e7ea4d-7db6-402c-ab24-824d068c3f8b_1679534876.419747.png)\n![image.png](https://assets.leetcode.com/users/images/a37283db-05c2-4b24-bfe9-d19998fbbc7b_1679534911.6596534.png)\n![image.png](https://assets.leetcode.com/users/images/7f6fdd0a-3e70-4f57-8aaa-57a2da392761_1679534936.9420202.png)\nAlthough the same problem of finding number of component can be solved by `BFS`, `DFS` & also with help of `Union Find` but DFS is the most easiest and intuitive way.\n![image.png](https://assets.leetcode.com/users/images/6322fadc-c5f6-4438-80d9-b39d6a3ec9d7_1679536214.2747602.png)\n![image.png](https://assets.leetcode.com/users/images/77e241ff-a1ef-4604-9aa6-07da8cbf97e0_1679536048.559381.png)\n![image.png](https://assets.leetcode.com/users/images/710ed5d2-9162-4184-8257-138ec74c2fc5_1679536073.5923595.png)\n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    void dfs(vector<vector<int>> &adj, vector<bool> &visited, int src){\n        visited[src] = true;\n        for(int i : adj[src])\n            if(!visited[i])\n                dfs(adj, visited, i);\n    }\n\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        if(connections.size() < n - 1) return -1;\n        vector<vector<int>> adj(n);\n        for(auto c : connections){\n            adj[c[0]].push_back(c[1]);\n            adj[c[1]].push_back(c[0]);\n        }\n\n        vector<bool> visited(n, false);\n        int components = 0;\n        for(int i=0; i<n; i++)\n            if(!visited[i]){\n                dfs(adj, visited, i);\n                components++;\n            }\n        return components - 1;\n    }\n};\n```\n```Java []\nclass Solution {\n    int dfs(int u, List<Integer>[] graph, boolean[] visited) {\n        if (visited[u]) return 0;\n        visited[u] = true;\n        for (int v : graph[u]) dfs(v, graph, visited);\n        return 1;\n    }\n\n    public int makeConnected(int n, int[][] connections) {\n        if (connections.length < n - 1) return -1;\n        List<Integer>[] graph = new List[n];\n        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();\n        for (int[] c : connections) {\n            graph[c[0]].add(c[1]);\n            graph[c[1]].add(c[0]);\n        }\n        \n        int components = 0;\n        boolean[] visited = new boolean[n];\n        for (int v = 0; v < n; v++) components += dfs(v, graph, visited);\n        return components - 1;\n    }\n}\n```\n```Python []\nclass Solution:\n    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n        if len(connections) < n - 1: return -1\n        \n        graph = [set() for i in range(n)]\n        for u, v in connections:\n            graph[u].add(v)\n            graph[v].add(u)\n        visited = [0] * n\n\n        def dfs(node):\n            if visited[node]: return 0\n            visited[node] = 1\n            for neighbor in graph[node]: dfs(neighbor)\n            return 1\n\n        return sum(dfs(node) for node in range(n)) - 1\n```\n
['Depth-First Search', 'Graph', 'Python', 'C++', 'Java']