fork download
copy 
  1. /*
  2. QUESTION 11: Amazon HackOn OA — Maximizing Reachability by Reversing Edges
  3.  
  4. Problem Statement:
  5. You are given a directed graph.
  6.  
  7. You may reverse the direction of at most two existing directed edges.
  8.  
  9. After doing this, define the score as:
  10. the number of ordered pairs (u, v) such that v is reachable from u.
  11.  
  12. Return the maximum score possible.
  13.  
  14. Hard Constraints:
  15. 1 <= N <= 120
  16. 1 <= M <= 300
  17.  
  18. Example:
  19. N = 4
  20. Edges:
  21. 1 -> 2
  22. 3 -> 2
  23. 3 -> 4
  24.  
  25. Expected Output:
  26. 10
  27.  
  28. Explanation:
  29. Reverse edge 3 -> 2 into 2 -> 3.
  30.  
  31. Then the graph becomes:
  32. 1 -> 2 -> 3 -> 4
  33.  
  34. Reachable ordered pairs including self-pairs:
  35. 1 can reach 1,2,3,4
  36. 2 can reach 2,3,4
  37. 3 can reach 3,4
  38. 4 can reach 4
  39.  
  40. Total = 10
  41.  
  42. Brute Force:
  43. Try:
  44. - reversing no edge
  45. - reversing one edge
  46. - reversing every pair of edges
  47.  
  48. For every modified graph, run DFS/BFS from every node and count reachable pairs.
  49.  
  50. Time Complexity:
  51. O(M^2 * N * (N + M))
  52.  
  53. Optimized Approach:
  54. Still enumerate edge choices because at most two edges are reversed.
  55.  
  56. For each modified graph, compute reachability using bitset transitive closure.
  57.  
  58. reach[i] stores all nodes reachable from i.
  59. If i can reach k:
  60. reach[i] |= reach[k]
  61.  
  62. Time Complexity:
  63. O(M^2 * N^3 / 64)
  64.  
  65. Space Complexity:
  66. O(N^2 / 64)
  67. */
  68.  
  69. #include <bits/stdc++.h>
  70. using namespace std;
  71.  
  72. class Solution {
  73. public:
  74.     long long countReachable(int n,
  75.                              vector<pair<int, int>>& edges,
  76.                              int reverseA,
  77.                              int reverseB) {
  78.  
  79.         vector<bitset<125>> reach(n);
  80.  
  81.         for (int i = 0; i < n; i++) {
  82.             reach[i][i] = 1;
  83.         }
  84.  
  85.         for (int i = 0; i < (int)edges.size(); i++) {
  86.             int u = edges[i].first;
  87.             int v = edges[i].second;
  88.  
  89.             if (i == reverseA || i == reverseB) {
  90.                 swap(u, v);
  91.             }
  92.  
  93.             reach[u][v] = 1;
  94.         }
  95.  
  96.         for (int k = 0; k < n; k++) {
  97.             for (int i = 0; i < n; i++) {
  98.                 if (reach[i][k]) {
  99.                     reach[i] |= reach[k];
  100.                 }
  101.             }
  102.         }
  103.  
  104.         long long total = 0;
  105.  
  106.         for (int i = 0; i < n; i++) {
  107.             total += reach[i].count();
  108.         }
  109.  
  110.         return total;
  111.     }
  112.  
  113.     long long maximizeReachablePairs(int n, vector<pair<int, int>>& edges) {
  114.         int m = edges.size();
  115.  
  116.         for (auto &e : edges) {
  117.             e.first--;
  118.             e.second--;
  119.         }
  120.  
  121.         long long ans = countReachable(n, edges, -1, -1);
  122.  
  123.         for (int i = 0; i < m; i++) {
  124.             ans = max(ans, countReachable(n, edges, i, -1));
  125.         }
  126.  
  127.         for (int i = 0; i < m; i++) {
  128.             for (int j = i + 1; j < m; j++) {
  129.                 ans = max(ans, countReachable(n, edges, i, j));
  130.             }
  131.         }
  132.  
  133.         return ans;
  134.     }
  135. };
  136.  
  137. int main() {
  138.     Solution sol;
  139.  
  140.     int n = 4;
  141.     vector<pair<int, int>> edges = {
  142.         {1, 2},
  143.         {3, 2},
  144.         {3, 4}
  145.     };
  146.  
  147.     cout << sol.maximizeReachablePairs(n, edges) << endl;
  148.  
  149.     return 0;
  150. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10
https://ideone.com/Bfsaum
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!