Maximizing Reachable Nodes Across Two Graphs Using DFS
IntuitionThe problem involves finding the maximum number of target nodes reachable in two graphs given a certain depth. We use Depth First Search (DFS) to explo
# Intuition\nThe problem involves finding the maximum number of target nodes reachable in two graphs given a certain depth. We use Depth First Search (DFS) to explore the graphs and determine the count of reachable nodes. Combining the results from both graphs allows us to compute the desired maximum target nodes.\n\n# Approach\n1. Represent the two graphs as adjacency lists.\n2. Use a DFS function to explore nodes up to a depth `k` and count the reachable nodes.\n3. For each node in the second graph, compute the maximum number of nodes reachable.\n4. For each node in the first graph, compute the total reachable nodes by adding the DFS result for that node and the maximum result from the second graph.\n5. Return the results as a vector.\n\n# Complexity\n- **Time complexity:**\n  - Building adjacency lists: $$O(E_1 + E_2)$$, where $$E_1$$ and $$E_2$$ are the number of edges in the two graphs.\n  - Performing DFS for each node: $$O((V_1 + V_2) \\times k)$$, where $$V_1$$ and $$V_2$$ are the number of nodes in the two graphs, and $$k$$ is the depth limit.\n  - Overall: $$O(E_1 + E_2 + (V_1 + V_2) \\times k)$$.\n- **Space complexity:**\n  - Storing adjacency lists: $$O(E_1 + E_2)$$.\n  - Recursion stack for DFS: $$O(k)$$.\n  - Visited arrays: $$O(V_1 + V_2)$$.\n  - Overall: $$O(E_1 + E_2 + V_1 + V_2)$$.\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int dfs(vector<vector<int>>& adj, int source, int level, vector<int>& visited, int k) {\n        if (k == 0) return 1; // Base case: depth 0 reached\n        if (k < 0) return 0;  // Invalid depth\n        if (k == level) return 1; // Reached the required depth\n        if (visited[source]) return 0; // Already visited\n\n        visited[source] = true; // Mark as visited\n        int sum = 0;\n        for (auto next : adj[source]) {\n            if (visited[next]) continue; // Skip already visited nodes\n            sum += dfs(adj, next, level + 1, visited, k); // Recursive DFS\n        }\n        visited[source] = false; // Backtrack\n        return sum + 1; // Include the current node\n    }\n\n    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {\n        int n = edges1.size() + 1; // Number of nodes in the first graph\n        int m = edges2.size() + 1; // Number of nodes in the second graph\n\n        // Build adjacency lists\n        vector<vector<int>> adj1(n);\n        vector<vector<int>> adj2(m);\n        for (auto edge : edges1) {\n            int u = edge[0], v = edge[1];\n            adj1[u].push_back(v);\n            adj1[v].push_back(u);\n        }\n        for (auto edge : edges2) {\n            int u = edge[0], v = edge[1];\n            adj2[u].push_back(v);\n            adj2[v].push_back(u);\n        }\n\n        // Find the maximum reachable nodes in the second graph\n        int max2 = INT_MIN;\n        for (int i = 0; i < m; i++) {\n            vector<int> visited(m, false);\n            max2 = max(max2, dfs(adj2, i, 0, visited, k - 1));\n        }\n\n        // Compute the results for the first graph\n        vector<int> answer(n);\n        for (int i = 0; i < n; i++) {\n            vector<int> visited(n, false);\n            int res = dfs(adj1, i, 0, visited, k);\n            answer[i] = res + max2;\n        }\n\n        return answer;\n    }\n};\n
['C++']