Day 82 || DFS || Easiest Beginner Friendly Sol
NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.\n\n# Intuitio
**NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Intuition of this Problem :\nThe logic behind the code is to use depth-first search (DFS) to traverse the network and count the number of connected components. We can use DFS to find all the computers that are reachable from a given computer, and mark them as visited.\n\nThe DFS function takes the network, the visited vector, and the index of the source computer as input. It first marks the source computer as visited, and then iterates through all the adjacent computers of the source computer. For each unvisited adjacent computer, the DFS function is called recursively.\n\nIn the main function, we iterate through all the computers in the network, and call the DFS function on each unvisited computer. For each call to the DFS function, we increment a counter that keeps track of the number of connected components in the network.\n\nFinally, we return the number of connected components minus one, since we need to perform one operation to connect each component.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach for this Problem :\n1. If the size of connections is less than n - 1, return -1.\n2. Create an adjacency list for each computer.\n3. Create a visited boolean vector of size n.\n4. Initialize minOperations to zero.\n5. For each computer in the network:\n    - a. If the computer is not visited, perform dfs on the network starting from that computer.\n    - b. Mark all the visited computers.\n    - c. Increment minOperations by one.\n1. Return minOperations - 1 as the minimum number of operations.\n<!-- Describe your approach to solving the problem. -->\n\n# Code :\n```C++ []\nclass Solution {\npublic:\n    void dfs(vector<vector<int>>& network, vector<bool>& visited, int srcComputer) {\n        visited[srcComputer] = true;\n        for (int adjComputer : network[srcComputer]) {\n            if (!visited[adjComputer]) {\n                dfs(network, visited, adjComputer);  \n            }\n        }\n    }\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        if (connections.size() < n - 1)\n            return -1;\n        vector<vector<int>> network(n);\n        for (auto connection : connections) {\n            network[connection[0]].push_back(connection[1]);\n            network[connection[1]].push_back(connection[0]);\n        }\n        //this type of dfs pattern we generally use when we want to find our ans in disconnected part\n        vector<bool> visited(n, false);\n        int minOperations = 0;\n        for (int computer = 0; computer < n; computer++) {\n            if (!visited[computer]) {\n                dfs(network, visited, computer);\n                minOperations++;\n            }\n        }\n        return minOperations - 1;\n    }\n};\n```\n```Java []\nclass Solution {\n    public void dfs(List<List<Integer>> network, boolean[] visited, int srcComputer) {\n        visited[srcComputer] = true;\n        for (int adjComputer : network.get(srcComputer)) {\n            if (!visited[adjComputer]) {\n                dfs(network, visited, adjComputer);  \n            }\n        }\n    }\n    \n    public int makeConnected(int n, List<List<Integer>> connections) {\n        if (connections.size() < n - 1)\n            return -1;\n        \n        List<List<Integer>> network = new ArrayList<>(n);\n        for (int i = 0; i < n; i++) {\n            network.add(new ArrayList<>());\n        }\n        \n        for (List<Integer> connection : connections) {\n            network.get(connection.get(0)).add(connection.get(1));\n            network.get(connection.get(1)).add(connection.get(0));\n        }\n        \n        boolean[] visited = new boolean[n];\n        int minOperations = 0;\n        for (int computer = 0; computer < n; computer++) {\n            if (!visited[computer]) {\n                dfs(network, visited, computer);\n                minOperations++;\n            }\n        }\n        return minOperations - 1;\n    }\n}\n\n```\n```Python []\nclass Solution:\n    def dfs(self, network, visited, srcComputer):\n        visited[srcComputer] = True\n        for adjComputer in network[srcComputer]:\n            if not visited[adjComputer]:\n                self.dfs(network, visited, adjComputer)\n    \n    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n        if len(connections) < n - 1:\n            return -1\n        \n        network = [[] for i in range(n)]\n        for connection in connections:\n            network[connection[0]].append(connection[1])\n            network[connection[1]].append(connection[0])\n        \n        visited = [False] * n\n        minOperations = 0\n        for computer in range(n):\n            if not visited[computer]:\n                self.dfs(network, visited, computer)\n                minOperations += 1\n        \n        return minOperations - 1\n\n```\n\n# Time Complexity and Space Complexity:\n- **Time complexity :** \n\nThe time complexity of the algorithm depends on the number of edges and vertices in the network. The dfs function visits each vertex at most once, and for each vertex, it visits all its adjacent vertices. Therefore, the time complexity of the dfs function is **O(V + E), where V is the number of vertices and E is the number of edges in the network.**\n\nIn the main function, we perform dfs for each unvisited computer in the network, which takes O(V + E) time. Therefore, the total time complexity of the algorithm is **O(V + E), where V is the number of computers and E is the number of connections.**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- **Space complexity :**\n\nThe space complexity of the algorithm depends on the size of the input and the size of the auxiliary data structures used.\n\nWe use a boolean vector of size n to keep track of visited computers, so the space complexity is O(n).\n\nWe also use an adjacency list to represent the network, which takes O(E) space, where E is the number of connections.\n\nTherefore, **the total space complexity of the algorithm is O(n + E).**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Depth-First Search', 'Graph', 'C++', 'Java', 'Python3']