fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. // ===================================================================
  7. // This file contains a collection of algorithms related to bipartite
  8. // graphs and assignment problems:
  9. //   - Maximum Bipartite Matching (Kuhn & Hopcroft‑Karp)
  10. //   - Minimum Vertex Cover & Maximum Independent Set (König)
  11. //   - Hungarian Algorithm (Assignment Problem)
  12. //   - Utilities: bipartiteness check, DAG path cover, small‑right matching
  13. // All functions are ready to be used as "black boxes".
  14. // Read the comments above each one to understand:
  15. //   - What it solves
  16. //   - What input it expects
  17. //   - What it returns
  18. //   - Time complexity
  19. //   - Important constraints / assumptions
  20. // ===================================================================
  21.  
  22. // -------------------------------------------------------------------
  23. // TERMINOLOGY (explained in simple English)
  24. // -------------------------------------------------------------------
  25. // Bipartite graph  : vertices split into Left (L) and Right (R), all edges
  26. //                    connect L to R.
  27. // Matching         : a set of edges with no shared vertices.
  28. // Maximum matching : largest possible number of matching edges.
  29. // Perfect matching : covers every vertex (requires |L| = |R|).
  30. // Alternating path : starts/ends with unmatched edges, alternates.
  31. // Augmenting path  : alternating path from unmatched L to unmatched R.
  32. //                    Flipping its edges increases matching size by 1.
  33. // Vertex cover     : a set of vertices that touches every edge.
  34. // König's theorem  : in bipartite graphs, max matching size = min vertex cover size.
  35. // Independent set  : a set of vertices with no edges between them.
  36. // Assignment problem: assign each left vertex to a distinct right vertex
  37. //                     minimizing total cost (or maximizing profit).
  38. // Hungarian algorithm: solves the assignment problem in O(n³).
  39. // Hopcroft‑Karp   : faster matching algorithm O(E√V).
  40. // ===================================================================
  41.  
  42. // ===================================================================
  43. // 1) Maximum Bipartite Matching – Kuhn's Algorithm (DFS augmenting)
  44. // ===================================================================
  45.  
  46. // 1.1) DFS helper for Kuhn. Do not call directly.
  47. //      Tries to find an augmenting path starting from left vertex `v`.
  48. //      Returns true if it succeeds.
  49. bool try_kuhn(int v, const vector<vector<int>>& adj,
  50.               vector<int>& matchR, vector<int>& vis) {
  51.     if (vis[v]) return false;
  52.     vis[v] = 1;
  53.     for (int to : adj[v]) {
  54.         if (matchR[to] == -1 || try_kuhn(matchR[to], adj, matchR, vis)) {
  55.             matchR[to] = v;
  56.             return true;
  57.         }
  58.     }
  59.     return false;
  60. }
  61.  
  62. // 1.2) Maximum Bipartite Matching using Kuhn's algorithm.
  63. //      INPUT:
  64. //        - n : number of left vertices (0 .. n-1)
  65. //        - m : number of right vertices (0 .. m-1)
  66. //        - adj : adjacency list of size n; adj[i] contains right neighbours
  67. //      OUTPUT:
  68. //        - Returns the size of the maximum matching.
  69. //        - Optionally fills `matchR_out`: matchR[r] = left matched to right r,
  70. //          or -1 if unmatched.
  71. //      TIME COMPLEXITY: O(n * E), where E = total edges.
  72. //                       Fast for n,m <= 5000 in practice.
  73. //      CONSTRAINTS:
  74. //        - Graph must be bipartite (assumed).
  75. //        - Edges are unweighted.
  76. //      NOTES:
  77. //        - Does not modify the input graph.
  78. //        - For larger graphs (n,m up to 50000), use hopcroftKarp().
  79. int maxBipartiteMatching(int n, int m, const vector<vector<int>>& adj,
  80.                          vector<int>* matchR_out = nullptr) {
  81.     vector<int> matchR(m, -1);
  82.     int matching = 0;
  83.     for (int v = 0; v < n; v++) {
  84.         vector<int> vis(n, 0);
  85.         if (try_kuhn(v, adj, matchR, vis))
  86.             matching++;
  87.     }
  88.     if (matchR_out) *matchR_out = matchR;
  89.     return matching;
  90. }
  91.  
  92. // ===================================================================
  93. // 2) Minimum Vertex Cover in a Bipartite Graph (König's Theorem)
  94. // ===================================================================
  95.  
  96. // 2.1) Compute a minimum vertex cover given a maximum matching.
  97. //      INPUT:
  98. //        - n, m : sizes of left and right parts
  99. //        - adj  : original adjacency list (left -> right)
  100. //        - matchR : vector of size m from a maximum matching
  101. //      OUTPUT:
  102. //        - Returns a pair (leftCover, rightCover) of vertex IDs.
  103. //      TIME COMPLEXITY: O(n + m + E)
  104. //      CONSTRAINTS:
  105. //        - matchR must be a valid maximum matching.
  106. //      NOTES:
  107. //        - Size of leftCover + rightCover equals matching size.
  108. pair<vector<int>, vector<int>> minVertexCover(
  109.     int n, int m,
  110.     const vector<vector<int>>& adj,
  111.     const vector<int>& matchR) {
  112.  
  113.     vector<int> matchedLeft(n, 0);
  114.     for (int r = 0; r < m; r++)
  115.         if (matchR[r] != -1)
  116.             matchedLeft[matchR[r]] = 1;
  117.  
  118.     vector<int> visL(n, 0), visR(m, 0);
  119.     queue<int> q;
  120.     for (int l = 0; l < n; l++) {
  121.         if (!matchedLeft[l]) {
  122.             visL[l] = 1;
  123.             q.push(l);
  124.         }
  125.     }
  126.  
  127.     while (!q.empty()) {
  128.         int l = q.front(); q.pop();
  129.         for (int r : adj[l]) {
  130.             if (!visR[r]) {
  131.                 visR[r] = 1;
  132.                 if (matchR[r] != -1 && !visL[matchR[r]]) {
  133.                     visL[matchR[r]] = 1;
  134.                     q.push(matchR[r]);
  135.                 }
  136.             }
  137.         }
  138.     }
  139.  
  140.     vector<int> leftCover, rightCover;
  141.     for (int l = 0; l < n; l++)
  142.         if (!visL[l]) leftCover.push_back(l);
  143.     for (int r = 0; r < m; r++)
  144.         if (visR[r]) rightCover.push_back(r);
  145.  
  146.     return {leftCover, rightCover};
  147. }
  148.  
  149. // ===================================================================
  150. // 3) Maximum Independent Set in a Bipartite Graph
  151. // ===================================================================
  152.  
  153. // 3.1) Compute a maximum independent set.
  154. //      INPUT:
  155. //        - same as minVertexCover (n, m, adj, matchR from a maximum matching)
  156. //      OUTPUT:
  157. //        - Returns a vector of vertex IDs (0 .. n+m-1). Left vertices are
  158. //          encoded as their index; right vertices as n + r.
  159. //      TIME COMPLEXITY: O(n + m + E)
  160. //      NOTES:
  161. //        - Complement of a minimum vertex cover.
  162. //        - Size = (n + m) - matching_size.
  163. vector<int> maxIndependentSet(
  164.     int n, int m,
  165.     const vector<vector<int>>& adj,
  166.     const vector<int>& matchR) {
  167.  
  168.     auto [lc, rc] = minVertexCover(n, m, adj, matchR);
  169.  
  170.     vector<int> inCover(n + m, 0);
  171.     for (int l : lc) inCover[l] = 1;
  172.     for (int r : rc) inCover[n + r] = 1;
  173.  
  174.     vector<int> independent;
  175.     for (int v = 0; v < n + m; v++) {
  176.         if (!inCover[v]) independent.push_back(v);
  177.     }
  178.     return independent;
  179. }
  180.  
  181. // ===================================================================
  182. // 4) Hungarian Algorithm (Kuhn‑Munkres) for Assignment Problem
  183. // ===================================================================
  184.  
  185. // 4.1) Solve the minimum cost perfect assignment (square matrix).
  186. //      INPUT:
  187. //        - a : n x n matrix of costs (long long). a[i][j] = cost of
  188. //              assigning left i to right j.
  189. //      OUTPUT:
  190. //        - Returns {min_cost, assignment}. assignment[i] = j means
  191. //          left i is assigned to right j.
  192. //      TIME COMPLEXITY: O(n³)
  193. //      CONSTRAINTS:
  194. //        - n >= 1, matrix must be square.
  195. //        - Costs can be negative (handled correctly).
  196. //      NOTES:
  197. //        - For rectangular matrices, add dummy rows/columns with zero cost.
  198. //        - To maximize profit, see maxWeightAssignment() below.
  199. pair<ll, vector<int>> hungarian(const vector<vector<ll>>& a) {
  200.     int n = (int)a.size();
  201.     int m = (int)a[0].size(); // must be n
  202.     vector<ll> u(n + 1), v(m + 1);
  203.     vector<int> p(m + 1), way(m + 1);
  204.  
  205.     for (int i = 1; i <= n; i++) {
  206.         p[0] = i;
  207.         int j0 = 0;
  208.         vector<ll> minv(m + 1, LLONG_MAX);
  209.         vector<int> used(m + 1, 0);
  210.         do {
  211.             used[j0] = 1;
  212.             int i0 = p[j0];
  213.             ll delta = LLONG_MAX;
  214.             int j1 = 0;
  215.             for (int j = 1; j <= m; j++) {
  216.                 if (!used[j]) {
  217.                     ll cur = a[i0 - 1][j - 1] - u[i0] - v[j];
  218.                     if (cur < minv[j]) {
  219.                         minv[j] = cur;
  220.                         way[j] = j0;
  221.                     }
  222.                     if (minv[j] < delta) {
  223.                         delta = minv[j];
  224.                         j1 = j;
  225.                     }
  226.                 }
  227.             }
  228.             for (int j = 0; j <= m; j++) {
  229.                 if (used[j]) {
  230.                     u[p[j]] += delta;
  231.                     v[j] -= delta;
  232.                 } else {
  233.                     minv[j] -= delta;
  234.                 }
  235.             }
  236.             j0 = j1;
  237.         } while (p[j0] != 0);
  238.  
  239.         // augmenting
  240.         do {
  241.             int j1 = way[j0];
  242.             p[j0] = p[j1];
  243.             j0 = j1;
  244.         } while (j0);
  245.     }
  246.  
  247.     vector<int> assignment(n);
  248.     for (int j = 1; j <= m; j++) {
  249.         if (p[j] > 0)
  250.             assignment[p[j] - 1] = j - 1;
  251.     }
  252.     ll cost = 0;
  253.     for (int i = 0; i < n; i++) cost += a[i][assignment[i]];
  254.     return {cost, assignment};
  255. }
  256.  
  257. // ===================================================================
  258. // 5) Hopcroft‑Karp Algorithm – Faster Maximum Bipartite Matching
  259. // ===================================================================
  260.  
  261. // 5.1) Hopcroft‑Karp for maximum bipartite matching.
  262. //      INPUT:
  263. //        - n, m, adj (same as Kuhn)
  264. //      OUTPUT:
  265. //        - Returns matching size.
  266. //        - Optionally fills matchR_out.
  267. //      TIME COMPLEXITY: O(E * sqrt(V)) where V = n + m.
  268. //      CONSTRAINTS:
  269. //        - Graph is bipartite.
  270. //      NOTES:
  271. //        - Use this when n,m are large (e.g., 50000) and E moderate.
  272. int hopcroftKarp(int n, int m, const vector<vector<int>>& adj,
  273.                  vector<int>* matchR_out = nullptr) {
  274.     vector<int> pairU(n, -1), pairV(m, -1), dist(n);
  275.  
  276.     auto bfs = [&]() -> bool {
  277.         queue<int> q;
  278.         for (int u = 0; u < n; u++) {
  279.             if (pairU[u] == -1) {
  280.                 dist[u] = 0;
  281.                 q.push(u);
  282.             } else {
  283.                 dist[u] = -1;
  284.             }
  285.         }
  286.         bool found = false;
  287.         while (!q.empty()) {
  288.             int u = q.front(); q.pop();
  289.             for (int v : adj[u]) {
  290.                 int u_next = pairV[v];
  291.                 if (u_next == -1) {
  292.                     found = true;
  293.                 } else if (dist[u_next] == -1) {
  294.                     dist[u_next] = dist[u] + 1;
  295.                     q.push(u_next);
  296.                 }
  297.             }
  298.         }
  299.         return found;
  300.     };
  301.  
  302.     function<bool(int)> dfs = [&](int u) -> bool {
  303.         for (int v : adj[u]) {
  304.             int u_next = pairV[v];
  305.             if (u_next == -1 || (dist[u_next] == dist[u] + 1 && dfs(u_next))) {
  306.                 pairU[u] = v;
  307.                 pairV[v] = u;
  308.                 return true;
  309.             }
  310.         }
  311.         dist[u] = -1;
  312.         return false;
  313.     };
  314.  
  315.     int matching = 0;
  316.     while (bfs()) {
  317.         for (int u = 0; u < n; u++) {
  318.             if (pairU[u] == -1 && dfs(u))
  319.                 matching++;
  320.         }
  321.     }
  322.  
  323.     if (matchR_out) {
  324.         matchR_out->assign(m, -1);
  325.         for (int u = 0; u < n; u++) {
  326.             if (pairU[u] != -1)
  327.                 (*matchR_out)[pairU[u]] = u;
  328.         }
  329.     }
  330.     return matching;
  331. }
  332.  
  333. // ===================================================================
  334. // 6) Utilities for Bipartite Graphs
  335. // ===================================================================
  336.  
  337. // 6.1) Check if a graph is bipartite and return the two partitions.
  338. //      INPUT:
  339. //        - V : number of vertices (0 .. V-1)
  340. //        - adj : undirected adjacency list (each edge appears twice)
  341. //      OUTPUT:
  342. //        - Returns true if bipartite.
  343. //        - If true, fills `color` with 0/1 for each vertex.
  344. //      TIME COMPLEXITY: O(V + E)
  345. bool isBipartite(int V, const vector<vector<int>>& adj, vector<int>& color) {
  346.     color.assign(V, -1);
  347.     queue<int> q;
  348.     for (int start = 0; start < V; start++) {
  349.         if (color[start] != -1) continue;
  350.         color[start] = 0;
  351.         q.push(start);
  352.         while (!q.empty()) {
  353.             int u = q.front(); q.pop();
  354.             for (int v : adj[u]) {
  355.                 if (color[v] == -1) {
  356.                     color[v] = color[u] ^ 1;
  357.                     q.push(v);
  358.                 } else if (color[v] == color[u]) {
  359.                     return false;
  360.                 }
  361.             }
  362.         }
  363.     }
  364.     return true;
  365. }
  366.  
  367. // 6.2) Build left adjacency list from an undirected bipartite graph.
  368. //      INPUT:
  369. //        - V, adj, color (from isBipartite, color 0 = left, 1 = right)
  370. //      OUTPUT:
  371. //        - Returns {leftAdj, R}. leftAdj has size L (count of color 0),
  372. //          each entry contains compressed right IDs (0..R-1).
  373. //      TIME COMPLEXITY: O(V + E)
  374. pair<vector<vector<int>>, int> buildBipartiteAdj(
  375.     int V,
  376.     const vector<vector<int>>& adj,
  377.     const vector<int>& color) {
  378.  
  379.     vector<int> leftId(V, -1), rightId(V, -1);
  380.     int L = 0, R = 0;
  381.     for (int i = 0; i < V; i++) {
  382.         if (color[i] == 0) leftId[i] = L++;
  383.         else rightId[i] = R++;
  384.     }
  385.  
  386.     vector<vector<int>> leftAdj(L);
  387.     for (int u = 0; u < V; u++) {
  388.         if (color[u] == 0) {
  389.             int l = leftId[u];
  390.             for (int v : adj[u]) {
  391.                 if (color[v] == 1) {
  392.                     leftAdj[l].push_back(rightId[v]);
  393.                 }
  394.             }
  395.         }
  396.     }
  397.     return {leftAdj, R};
  398. }
  399.  
  400. // ===================================================================
  401. // 7) Advanced Patterns & Tricks
  402. // ===================================================================
  403.  
  404. // 7.1) Maximum matching when the right side is very small (m <= 20).
  405. //      INPUT:
  406. //        - n : number of left vertices
  407. //        - m : number of right vertices (must be <= 20)
  408. //        - adjMask : vector of size n, where bit r is set if left i
  409. //                    connects to right r.
  410. //      OUTPUT:
  411. //        - Returns maximum matching size.
  412. //      TIME COMPLEXITY: O(n * 2^m)
  413. //      CONSTRAINTS:
  414. //        - m <= 20 (fits in 32‑bit int).
  415. int maxMatchingSmallRight(int n, int m, const vector<int>& adjMask) {
  416.     int fullMask = 1 << m;
  417.     vector<int> dp(fullMask, -1);
  418.     dp[0] = 0;
  419.  
  420.     for (int i = 0; i < n; i++) {
  421.         vector<int> ndp = dp; // skip current left vertex
  422.         for (int mask = 0; mask < fullMask; mask++) {
  423.             if (dp[mask] == -1) continue;
  424.             int available = adjMask[i] & ~mask;
  425.             while (available) {
  426.                 int bit = available & -available;
  427.                 int newMask = mask | bit;
  428.                 ndp[newMask] = max(ndp[newMask], dp[mask] + 1);
  429.                 available -= bit;
  430.             }
  431.         }
  432.         dp.swap(ndp);
  433.     }
  434.  
  435.     int ans = 0;
  436.     for (int mask = 0; mask < fullMask; mask++) ans = max(ans, dp[mask]);
  437.     return ans;
  438. }
  439.  
  440. // 7.2) Minimum path cover in a Directed Acyclic Graph (DAG).
  441. //      INPUT:
  442. //        - V : number of vertices
  443. //        - dagEdges : vector of (u, v) directed edges (must be a DAG)
  444. //      OUTPUT:
  445. //        - Minimum number of vertex‑disjoint paths to cover all vertices.
  446. //      TIME COMPLEXITY: O(E * sqrt(V)) via Hopcroft‑Karp.
  447. //      NOTES:
  448. //        - By Dilworth's theorem: answer = V - max matching in the
  449. //          bipartite graph built from the DAG.
  450. int minPathCoverDAG(int V, const vector<pair<int,int>>& dagEdges) {
  451.     vector<vector<int>> adj(V);
  452.     for (auto [u, v] : dagEdges) {
  453.         adj[u].push_back(v);
  454.     }
  455.     vector<int> matchR;
  456.     int matching = hopcroftKarp(V, V, adj, &matchR);
  457.     return V - matching;
  458. }
  459.  
  460. // 7.3a) Maximum matching with forbidden edges: just use allowed edges only.
  461. //       This function is a reminder.
  462. int maxMatchingWithForbidden(int n, int m, const vector<vector<int>>& allowedEdges) {
  463.     return maxBipartiteMatching(n, m, allowedEdges);
  464. }
  465.  
  466. // 7.3b) Maximum weight perfect assignment (square matrix).
  467. //       INPUT:
  468. //         - cost : n x n matrix of profits (long long)
  469. //       OUTPUT:
  470. //         - Returns {max_profit, assignment}
  471. //       TIME COMPLEXITY: O(n³)
  472. //       NOTES:
  473. //         - If you have a rectangular matrix, add dummy rows/cols with zero.
  474. //         - For minimum cost, use hungarian() directly.
  475. pair<ll, vector<int>> maxWeightAssignment(const vector<vector<ll>>& cost) {
  476.     int n = (int)cost.size();
  477.     vector<vector<ll>> negCost(n, vector<ll>(n));
  478.     for (int i = 0; i < n; i++)
  479.         for (int j = 0; j < n; j++)
  480.             negCost[i][j] = -cost[i][j];
  481.     auto [minCost, assign] = hungarian(negCost);
  482.     return {-minCost, assign};
  483. }
  484.  
  485. // 7.4) Extract matching edges from the matchR array.
  486. //      INPUT:
  487. //        - matchR : vector of size m (right -> left) or -1 if unmatched
  488. //      OUTPUT:
  489. //        - Vector of pairs (left, right) for each matched edge.
  490. vector<pair<int,int>> extractMatchingEdges(const vector<int>& matchR) {
  491.     vector<pair<int,int>> edges;
  492.     for (int r = 0; r < (int)matchR.size(); r++) {
  493.         if (matchR[r] != -1) {
  494.             edges.push_back({matchR[r], r});
  495.         }
  496.     }
  497.     return edges;
  498. }
  499.  
  500. // ===================================================================
  501. // 8) Example usage (can be removed)
  502. // ===================================================================
  503.  
  504. int main() {
  505.     ios::sync_with_stdio(false);
  506.     cin.tie(nullptr);
  507.  
  508.     // Example: simple bipartite matching
  509.     int n = 2, m = 3;
  510.     vector<vector<int>> adj = {
  511.         {0, 1},
  512.         {1, 2}
  513.     };
  514.  
  515.     vector<int> matchR;
  516.     int matchSize = maxBipartiteMatching(n, m, adj, &matchR);
  517.     cout << "Maximum matching size: " << matchSize << "\n";
  518.     cout << "Assignments (right -> left):\n";
  519.     for (int r = 0; r < m; r++) {
  520.         cout << "right " << r << " -> left " << matchR[r] << "\n";
  521.     }
  522.  
  523.     // Minimum vertex cover
  524.     auto [lc, rc] = minVertexCover(n, m, adj, matchR);
  525.     cout << "Min vertex cover left: ";
  526.     for (int l : lc) cout << l << " ";
  527.     cout << "\nMin vertex cover right: ";
  528.     for (int r : rc) cout << r << " ";
  529.     cout << "\n";
  530.  
  531.     // Independent set
  532.     vector<int> indep = maxIndependentSet(n, m, adj, matchR);
  533.     cout << "Max independent set: ";
  534.     for (int v : indep) {
  535.         if (v < n) cout << "L" << v << " ";
  536.         else cout << "R" << (v - n) << " ";
  537.     }
  538.     cout << "\n";
  539.  
  540.     // Hungarian example
  541.     vector<vector<ll>> cost = {
  542.         {4, 1, 3},
  543.         {2, 0, 5},
  544.         {3, 2, 2}
  545.     };
  546.     auto [minCost, assign] = hungarian(cost);
  547.     cout << "Min assignment cost: " << minCost << "\n";
  548.     cout << "Assignment: ";
  549.     for (int i = 0; i < (int)assign.size(); i++)
  550.         cout << i << "->" << assign[i] << " ";
  551.     cout << "\n";
  552.  
  553.     return 0;
  554. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Maximum matching size: 2
Assignments (right -> left):
right 0 -> left 0
right 1 -> left 1
right 2 -> left -1
Min vertex cover left: 0 1 
Min vertex cover right: 
Max independent set: R0 R1 R2 
Min assignment cost: 5
Assignment: 0->1 1->0 2->2
https://ideone.com/zB6e7U
language:
C++ (gcc 8.3)
created:
1 day 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!