fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // ===================================================================
  5. // This file contains a collection of algorithms for Maximum Matching
  6. // in Bipartite Graphs, plus all related theorems and constructions
  7. // that frequently appear in ECPC / ACPC problems.
  8. //
  9. // All functions are written as "black boxes". Read the comments above
  10. // each one to understand:
  11. //   - What problem it solves
  12. //   - What input it expects
  13. //   - What it returns
  14. //   - Time complexity
  15. //   - Important constraints / assumptions
  16. //   - Any related concepts (explained in simple English)
  17. // ===================================================================
  18.  
  19. // ----------------------------- GLOSSARY -----------------------------
  20. // Bipartite Graph     : a graph whose vertices can be split into two
  21. //                       disjoint sets (Left and Right) such that every
  22. //                       edge connects a Left vertex to a Right vertex.
  23. // Matching            : a set of edges with no shared vertices.
  24. // Maximum Matching    : a matching with the largest possible number of
  25. //                       edges.
  26. // Augmenting Path     : a path that starts at an unmatched Left vertex,
  27. //                       ends at an unmatched Right vertex, and alternates
  28. //                       between unmatched and matched edges. Flipping
  29. //                       the edges along this path increases the matching
  30. //                       size by 1.
  31. // Vertex Cover        : a set of vertices that touches every edge.
  32. // Minimum Vertex Cover: the smallest vertex cover. In bipartite graphs,
  33. //                       its size equals the size of the maximum matching
  34. //                       (Kőnig's Theorem).
  35. // Independent Set     : a set of vertices with no edges between them.
  36. // Maximum Independent Set: the largest independent set. In bipartite
  37. //                       graphs, its size = total vertices – size of
  38. //                       minimum vertex cover.
  39. // ===================================================================
  40.  
  41. // ===================================================================
  42. // 1) Core Hopcroft‑Karp Maximum Bipartite Matching
  43. //    This is the fastest algorithm for maximum matching in bipartite
  44. //    graphs. It processes many augmenting paths in one BFS+DFS phase.
  45. // ===================================================================
  46.  
  47. // 1.1) Hopcroft‑Karp class (0‑based indexing)
  48. //      PURPOSE:
  49. //        Finds the maximum cardinality matching in a bipartite graph.
  50. //      HOW TO USE:
  51. //        1. Create an object: HopcroftKarp hk(n_left, n_right);
  52. //        2. Add edges: hk.add_edge(u, v);   // u in [0, n_left-1], v in [0, n_right-1]
  53. //        3. Get answer: int match_size = hk.max_matching();
  54. //        4. (Optional) Get the matched partner of each vertex:
  55. //           int left_match[u]  = hk.matchL[u];   // -1 if unmatched
  56. //           int right_match[v] = hk.matchR[v];   // -1 if unmatched
  57. //      TIME COMPLEXITY:
  58. //        O(E * sqrt(V)) where V = n_left + n_right, E = number of edges.
  59. //        This is much faster than the simple O(VE) Kuhn algorithm.
  60. //      CONSTRAINTS:
  61. //        - Graph must be bipartite (edges only from left to right).
  62. //        - Works for up to ~10^5 vertices and ~10^6 edges in practice.
  63. //      NOTES:
  64. //        - Uses 0‑based indexing internally.
  65. //        - If your graph is 1‑based, just subtract 1 when adding edges.
  66. //        - The algorithm is deterministic and returns the same result
  67. //          every time.
  68. struct HopcroftKarp {
  69.     int n_left, n_right;
  70.     vector<vector<int>> adj;          // adjacency list for left vertices
  71.     vector<int> matchL, matchR;       // matchL[u] = v matched to u, -1 if none
  72.     vector<int> dist;                 // distance used in BFS
  73.  
  74.     HopcroftKarp(int nL, int nR) : n_left(nL), n_right(nR) {
  75.         adj.resize(nL);
  76.         matchL.assign(nL, -1);
  77.         matchR.assign(nR, -1);
  78.         dist.resize(nL);
  79.     }
  80.  
  81.     void add_edge(int u, int v) {
  82.         adj[u].push_back(v);
  83.     }
  84.  
  85.     // BFS: builds layers of the alternating graph.
  86.     // Returns true if there is at least one augmenting path.
  87.     bool bfs() {
  88.         queue<int> q;
  89.         for (int u = 0; u < n_left; u++) {
  90.             if (matchL[u] == -1) {
  91.                 dist[u] = 0;
  92.                 q.push(u);
  93.             } else {
  94.                 dist[u] = -1;
  95.             }
  96.         }
  97.         bool found = false;
  98.         while (!q.empty()) {
  99.             int u = q.front(); q.pop();
  100.             for (int v : adj[u]) {
  101.                 int u2 = matchR[v];
  102.                 if (u2 == -1) {
  103.                     found = true;          // we reached an unmatched right vertex
  104.                 } else if (dist[u2] == -1) {
  105.                     dist[u2] = dist[u] + 1;
  106.                     q.push(u2);
  107.                 }
  108.             }
  109.         }
  110.         return found;
  111.     }
  112.  
  113.     // DFS: tries to find augmenting paths starting from u.
  114.     bool dfs(int u) {
  115.         for (int v : adj[u]) {
  116.             int u2 = matchR[v];
  117.             if (u2 == -1 || (dist[u2] == dist[u] + 1 && dfs(u2))) {
  118.                 matchL[u] = v;
  119.                 matchR[v] = u;
  120.                 return true;
  121.             }
  122.         }
  123.         dist[u] = -1;   // dead end – don't visit again in this phase
  124.         return false;
  125.     }
  126.  
  127.     // Returns the size of the maximum matching.
  128.     int max_matching() {
  129.         int matching = 0;
  130.         while (bfs()) {
  131.             for (int u = 0; u < n_left; u++) {
  132.                 if (matchL[u] == -1 && dfs(u)) {
  133.                     matching++;
  134.                 }
  135.             }
  136.         }
  137.         return matching;
  138.     }
  139. };
  140.  
  141. // ===================================================================
  142. // 2) Minimum Vertex Cover (using the matching from Hopcroft‑Karp)
  143. //    Kőnig's Theorem: In any bipartite graph, the size of the minimum
  144. //    vertex cover equals the size of the maximum matching.
  145. // ===================================================================
  146.  
  147. // 2.1) Minimum Vertex Cover – returns the set of vertices (as a pair
  148. //      of vectors: left vertices and right vertices) that cover all edges.
  149. //      PURPOSE:
  150. //        Given a bipartite graph, find the smallest set of vertices that
  151. //        touches every edge.
  152. //      HOW TO USE:
  153. //        1. Run HopcroftKarp to get the maximum matching.
  154. //        2. Call min_vertex_cover(hk, n_left, n_right) with the same
  155. //           HopcroftKarp object (after max_matching() has been called).
  156. //      RETURNS:
  157. //        A pair<vector<int>, vector<int>> where the first vector contains
  158. //        the left vertices in the cover, and the second contains the
  159. //        right vertices in the cover.
  160. //      TIME COMPLEXITY:
  161. //        O(V + E) after the matching is computed.
  162. //      CONSTRAINTS:
  163. //        - The HopcroftKarp object must have already computed the matching
  164. //          (i.e., max_matching() was called).
  165. //      NOTES:
  166. //        - The vertex cover is not necessarily unique; this function
  167. //          returns one valid minimum cover.
  168. //        - The size of the cover equals the matching size (you can verify
  169. //          this as a sanity check).
  170. pair<vector<int>, vector<int>> min_vertex_cover(const HopcroftKarp& hk) {
  171.     int nL = hk.n_left, nR = hk.n_right;
  172.     vector<bool> visitedL(nL, false), visitedR(nR, false);
  173.     queue<int> q;
  174.  
  175.     // Start BFS from all unmatched left vertices
  176.     for (int u = 0; u < nL; u++) {
  177.         if (hk.matchL[u] == -1) {
  178.             visitedL[u] = true;
  179.             q.push(u);
  180.         }
  181.     }
  182.  
  183.     // BFS on the alternating graph (using the matching)
  184.     while (!q.empty()) {
  185.         int u = q.front(); q.pop();
  186.         for (int v : hk.adj[u]) {
  187.             if (!visitedR[v]) {
  188.                 visitedR[v] = true;
  189.                 int u2 = hk.matchR[v];
  190.                 if (u2 != -1 && !visitedL[u2]) {
  191.                     visitedL[u2] = true;
  192.                     q.push(u2);
  193.                 }
  194.             }
  195.         }
  196.     }
  197.  
  198.     // Minimum vertex cover = (Left vertices NOT visited) ∪ (Right vertices visited)
  199.     vector<int> coverL, coverR;
  200.     for (int u = 0; u < nL; u++) {
  201.         if (!visitedL[u]) coverL.push_back(u);
  202.     }
  203.     for (int v = 0; v < nR; v++) {
  204.         if (visitedR[v]) coverR.push_back(v);
  205.     }
  206.     return {coverL, coverR};
  207. }
  208.  
  209. // ===================================================================
  210. // 3) Maximum Independent Set in a Bipartite Graph
  211. //    In any graph, the complement of a vertex cover is an independent set.
  212. //    So: Max Independent Set = All vertices – Min Vertex Cover.
  213. // ===================================================================
  214.  
  215. // 3.1) Maximum Independent Set – returns the set of vertices (as a pair
  216. //      of vectors: left and right) that form the largest independent set.
  217. //      PURPOSE:
  218. //        Find the largest set of vertices with no edges between any two
  219. //        of them.
  220. //      HOW TO USE:
  221. //        1. Run HopcroftKarp to get the matching.
  222. //        2. Call max_independent_set(hk) which internally uses the
  223. //           minimum vertex cover from above.
  224. //      RETURNS:
  225. //        A pair<vector<int>, vector<int>> containing the left and right
  226. //        vertices of the maximum independent set.
  227. //      TIME COMPLEXITY:
  228. //        O(V + E) after the matching is computed.
  229. //      CONSTRAINTS:
  230. //        - The HopcroftKarp object must have already computed the matching.
  231. //      NOTES:
  232. //        - The size of the independent set = total vertices – matching size.
  233. //        - This is a classic problem: e.g., "place the maximum number of
  234. //          non‑attacking rooks on a chessboard" often reduces to this.
  235. pair<vector<int>, vector<int>> max_independent_set(const HopcroftKarp& hk) {
  236.     auto cover = min_vertex_cover(hk);
  237.     vector<int> indL, indR;
  238.     // Left independent = left vertices NOT in coverL
  239.     // But careful: coverL contains left vertices that ARE in the cover.
  240.     // So independent left = all left – coverL.
  241.     vector<bool> inCoverL(hk.n_left, false);
  242.     for (int u : cover.first) inCoverL[u] = true;
  243.     for (int u = 0; u < hk.n_left; u++) {
  244.         if (!inCoverL[u]) indL.push_back(u);
  245.     }
  246.  
  247.     // Right independent = right vertices NOT in coverR
  248.     vector<bool> inCoverR(hk.n_right, false);
  249.     for (int v : cover.second) inCoverR[v] = true;
  250.     for (int v = 0; v < hk.n_right; v++) {
  251.         if (!inCoverR[v]) indR.push_back(v);
  252.     }
  253.     return {indL, indR};
  254. }
  255.  
  256. // ===================================================================
  257. // 4) Maximum Matching in a Bipartite Graph with 1‑based indexing
  258. //    (wrapper for convenience when the problem uses 1‑based vertices)
  259. // ===================================================================
  260.  
  261. // 4.1) Same as HopcroftKarp but everything is 1‑based.
  262. //      PURPOSE:
  263. //        Some problems index vertices from 1 to n. This wrapper adjusts
  264. //        the indexing so you can add edges directly with 1‑based numbers.
  265. //      HOW TO USE:
  266. //        1. Create: HopcroftKarp1 hk(n_left, n_right);
  267. //        2. Add edge: hk.add_edge(u, v);   // u in [1..n_left], v in [1..n_right]
  268. //        3. Get answer: int match_size = hk.max_matching();
  269. //        4. Get matches: matchL[u] (1‑based) or matchR[v] (1‑based).
  270. //      TIME COMPLEXITY:
  271. //        Same as the 0‑based version.
  272. //      NOTES:
  273. //        - Internally it converts to 0‑based, so the performance is identical.
  274. //        - The match arrays are 1‑based: matchL[1..n_left], matchR[1..n_right].
  275. struct HopcroftKarp1 {
  276.     int n_left, n_right;
  277.     vector<vector<int>> adj;
  278.     vector<int> matchL, matchR, dist;
  279.  
  280.     HopcroftKarp1(int nL, int nR) : n_left(nL), n_right(nR) {
  281.         adj.resize(nL + 1);          // 1‑based indexing
  282.         matchL.assign(nL + 1, 0);     // 0 means unmatched
  283.         matchR.assign(nR + 1, 0);
  284.         dist.resize(nL + 1);
  285.     }
  286.  
  287.     void add_edge(int u, int v) {
  288.         adj[u].push_back(v);
  289.     }
  290.  
  291.     bool bfs() {
  292.         queue<int> q;
  293.         for (int u = 1; u <= n_left; u++) {
  294.             if (matchL[u] == 0) {
  295.                 dist[u] = 0;
  296.                 q.push(u);
  297.             } else {
  298.                 dist[u] = -1;
  299.             }
  300.         }
  301.         bool found = false;
  302.         while (!q.empty()) {
  303.             int u = q.front(); q.pop();
  304.             for (int v : adj[u]) {
  305.                 int u2 = matchR[v];
  306.                 if (u2 == 0) {
  307.                     found = true;
  308.                 } else if (dist[u2] == -1) {
  309.                     dist[u2] = dist[u] + 1;
  310.                     q.push(u2);
  311.                 }
  312.             }
  313.         }
  314.         return found;
  315.     }
  316.  
  317.     bool dfs(int u) {
  318.         for (int v : adj[u]) {
  319.             int u2 = matchR[v];
  320.             if (u2 == 0 || (dist[u2] == dist[u] + 1 && dfs(u2))) {
  321.                 matchL[u] = v;
  322.                 matchR[v] = u;
  323.                 return true;
  324.             }
  325.         }
  326.         dist[u] = -1;
  327.         return false;
  328.     }
  329.  
  330.     int max_matching() {
  331.         int matching = 0;
  332.         while (bfs()) {
  333.             for (int u = 1; u <= n_left; u++) {
  334.                 if (matchL[u] == 0 && dfs(u)) {
  335.                     matching++;
  336.                 }
  337.             }
  338.         }
  339.         return matching;
  340.     }
  341. };
  342.  
  343. // ===================================================================
  344. // 5) Maximum Matching in a Bipartite Graph where one side is much smaller
  345. //    (Optimization: run BFS/DFS only on the smaller side)
  346. // ===================================================================
  347.  
  348. // 5.1) Hopcroft‑Karp that automatically uses the smaller side as "left"
  349. //      to reduce memory and time.
  350. //      PURPOSE:
  351. //        If the graph has, say, 1000 left vertices and 100,000 right
  352. //        vertices, we can swap the sides so that the BFS/DFS run on the
  353. //        smaller side. The matching size is the same.
  354. //      HOW TO USE:
  355. //        1. Create: HopcroftKarpOptimized hk(n_left, n_right);
  356. //        2. Add edge: hk.add_edge(u, v);
  357. //        3. Get matching: hk.max_matching();
  358. //      TIME COMPLEXITY:
  359. //        Same O(E sqrt(V)) but with a smaller constant if one side is tiny.
  360. //      NOTES:
  361. //        - The class internally decides which side is smaller and swaps
  362. //          if needed. You don't need to think about it.
  363. //        - The matchL/matchR arrays still use the original indexing.
  364. struct HopcroftKarpOptimized {
  365.     int nL, nR;
  366.     bool swapped;
  367.     vector<vector<int>> adj;   // adjacency from the side we treat as "left"
  368.     vector<int> matchL, matchR, dist;
  369.  
  370.     HopcroftKarpOptimized(int n_left, int n_right) {
  371.         if (n_left <= n_right) {
  372.             nL = n_left;
  373.             nR = n_right;
  374.             swapped = false;
  375.         } else {
  376.             nL = n_right;
  377.             nR = n_left;
  378.             swapped = true;
  379.         }
  380.         adj.resize(nL);
  381.         matchL.assign(nL, -1);
  382.         matchR.assign(nR, -1);
  383.         dist.resize(nL);
  384.     }
  385.  
  386.     void add_edge(int u, int v) {
  387.         if (!swapped) {
  388.             adj[u].push_back(v);
  389.         } else {
  390.             adj[v].push_back(u);   // swap sides
  391.         }
  392.     }
  393.  
  394.     bool bfs() {
  395.         queue<int> q;
  396.         for (int u = 0; u < nL; u++) {
  397.             if (matchL[u] == -1) {
  398.                 dist[u] = 0;
  399.                 q.push(u);
  400.             } else {
  401.                 dist[u] = -1;
  402.             }
  403.         }
  404.         bool found = false;
  405.         while (!q.empty()) {
  406.             int u = q.front(); q.pop();
  407.             for (int v : adj[u]) {
  408.                 int u2 = matchR[v];
  409.                 if (u2 == -1) {
  410.                     found = true;
  411.                 } else if (dist[u2] == -1) {
  412.                     dist[u2] = dist[u] + 1;
  413.                     q.push(u2);
  414.                 }
  415.             }
  416.         }
  417.         return found;
  418.     }
  419.  
  420.     bool dfs(int u) {
  421.         for (int v : adj[u]) {
  422.             int u2 = matchR[v];
  423.             if (u2 == -1 || (dist[u2] == dist[u] + 1 && dfs(u2))) {
  424.                 matchL[u] = v;
  425.                 matchR[v] = u;
  426.                 return true;
  427.             }
  428.         }
  429.         dist[u] = -1;
  430.         return false;
  431.     }
  432.  
  433.     int max_matching() {
  434.         int matching = 0;
  435.         while (bfs()) {
  436.             for (int u = 0; u < nL; u++) {
  437.                 if (matchL[u] == -1 && dfs(u)) {
  438.                     matching++;
  439.                 }
  440.             }
  441.         }
  442.         return matching;
  443.     }
  444.  
  445.     // Get the matched partner of original vertex u (0‑based)
  446.     int get_match(int u, bool is_left) {
  447.         if (!swapped) {
  448.             return is_left ? matchL[u] : matchR[u];
  449.         } else {
  450.             return is_left ? matchR[u] : matchL[u];
  451.         }
  452.     }
  453. };
  454.  
  455. // ===================================================================
  456. // 6) Check if a matching is perfect (covers all vertices on one side)
  457. // ===================================================================
  458.  
  459. // 6.1) Returns true if the matching covers all left vertices.
  460. //      PURPOSE:
  461. //        In many problems (e.g., assignment problems) you need to know
  462. //        if every left vertex can be matched.
  463. //      PARAMETERS:
  464. //        - hk: a HopcroftKarp object after max_matching() has been called.
  465. //      RETURNS:
  466. //        - true if every left vertex is matched, false otherwise.
  467. //      TIME COMPLEXITY:
  468. //        O(n_left)
  469. bool is_perfect_matching_left(const HopcroftKarp& hk) {
  470.     for (int u = 0; u < hk.n_left; u++) {
  471.         if (hk.matchL[u] == -1) return false;
  472.     }
  473.     return true;
  474. }
  475.  
  476. // 6.2) Returns true if the matching covers all right vertices.
  477. bool is_perfect_matching_right(const HopcroftKarp& hk) {
  478.     for (int v = 0; v < hk.n_right; v++) {
  479.         if (hk.matchR[v] == -1) return false;
  480.     }
  481.     return true;
  482. }
  483.  
  484. // ===================================================================
  485. // 7) Matching in a graph that is not explicitly bipartite
  486. //    (e.g., grid graphs, chessboard problems)
  487. // ===================================================================
  488.  
  489. // 7.1) Build a bipartite graph from a grid by colouring cells black/white.
  490. //      PURPOSE:
  491. //        Many problems (like placing dominoes, or knights on a chessboard)
  492. //        can be modelled as matching on a grid. The grid is bipartite
  493. //        by colouring it like a chessboard.
  494. //      HOW TO USE:
  495. //        - For each cell (i,j), compute id = i * cols + j.
  496. //        - If (i+j) is even, it's a "left" vertex; if odd, it's "right".
  497. //        - Add edges between adjacent cells (up/down/left/right).
  498. //      EXAMPLE:
  499. //        int rows, cols;
  500. //        auto id = [&](int i, int j) { return i * cols + j; };
  501. //        HopcroftKarp hk(rows * cols, rows * cols); // upper bound
  502. //        for each cell (i,j) with (i+j)%2 == 0:
  503. //            for each neighbour (ni,nj):
  504. //                hk.add_edge(id(i,j), id(ni,nj));
  505. //        int max_dominoes = hk.max_matching();
  506. //      NOTES:
  507. //        - The matching size gives the maximum number of dominoes (or
  508. //          knights, etc.) that can be placed.
  509. //        - This is a very common ECPC/ACPC pattern.
  510. // ===================================================================
  511.  
  512. // ===================================================================
  513. // 8) Maximum Matching with Binary Search (parametric matching)
  514. //    Often you need to find the smallest/largest value such that a
  515. //    matching of a certain size exists.
  516. // ===================================================================
  517.  
  518. // 8.1) Example: Given a threshold X, build a graph using only edges
  519. //      with weight <= X, then check if maximum matching size >= K.
  520. //      PURPOSE:
  521. //        When each edge has a cost/weight and you want the minimum
  522. //        possible maximum weight among a matching of size K.
  523. //      HOW TO USE:
  524. //        1. Sort all edges by weight.
  525. //        2. Binary search on the weight: for a given mid, add only edges
  526. //           with weight <= mid, run Hopcroft‑Karp, check if matching >= K.
  527. //      TIME COMPLEXITY:
  528. //        O(log W * E * sqrt(V)) where W is the range of weights.
  529. //      NOTES:
  530. //        - This is a classic "minimax" problem.
  531. //        - Appears in problems like "assign workers to jobs with minimum
  532. //          maximum cost".
  533. // ===================================================================
  534.  
  535. // ===================================================================
  536. // 9) Matching with vertex capacities (b‑matching)
  537. //    Sometimes each vertex can be matched more than once.
  538. // ===================================================================
  539.  
  540. // 9.1) For vertex capacities, you can split each vertex into multiple
  541. //      copies. For example, if a left vertex can be matched up to cap[u]
  542. //      times, create cap[u] copies of that vertex.
  543. //      PURPOSE:
  544. //        Handles problems where each worker can do multiple jobs, or each
  545. //        job needs multiple workers.
  546. //      HOW TO USE:
  547. //        - Build a new graph where each original vertex u is replaced by
  548. //          cap[u] identical vertices.
  549. //        - Run Hopcroft‑Karp on this expanded graph.
  550. //      TIME COMPLEXITY:
  551. //        O(E * sqrt(V)) where V is the total number of copies (sum of caps).
  552. //      NOTES:
  553. //        - This is a simple trick that often appears in ECPC problems.
  554. //        - If the capacities are large (e.g., up to 10^5), this may be
  555. //          too slow – then you need a flow‑based solution.
  556. // ===================================================================
  557.  
  558. // ===================================================================
  559. // 10) Maximum Matching in a Bipartite Graph with Holes / Missing Edges
  560. //     (e.g., "assign each left to a distinct right, but some pairs forbidden")
  561. // ===================================================================
  562.  
  563. // 10.1) Standard Hopcroft‑Karp handles missing edges by simply not adding
  564. //       them to the adjacency list. There's no special function needed.
  565. //       Just call add_edge only for allowed pairs.
  566. // ===================================================================
  567.  
  568. // ===================================================================
  569. // 11) Tricks & Patterns that appeared in ECPC/ACPC
  570. // ===================================================================
  571.  
  572. // 11.1) (Not a function)
  573. //       "Minimum number of edges to add to make a bipartite graph have
  574. //        a perfect matching" → This is the size of the maximum matching
  575. //        deficit. If max_matching < min(n_left, n_right), you need to add
  576. //        at least min(n_left, n_right) - max_matching edges.
  577. //       This appears in problems like "complete the assignment" or
  578. //       "minimum edges to add for full coverage".
  579.  
  580. // 11.2) (Not a function)
  581. //       "Maximum matching in a DAG" → A DAG (Directed Acyclic Graph)
  582. //       can be transformed into a bipartite graph by splitting each vertex
  583. //       into a left copy and a right copy. Then maximum matching gives
  584. //       the size of the minimum path cover.
  585. //       This is a very common trick in ECPC/ACPC (e.g., "minimum number
  586. //       of chains to cover all elements").
  587.  
  588. // 11.3) (Not a function)
  589. //       "Maximum matching with time windows" → Each left vertex can only
  590. //       be matched to a right vertex if a certain time condition holds.
  591. //       Often solved by sorting by time and using a greedy + Hopcroft‑Karp
  592. //       or by building the graph dynamically.
  593.  
  594. // 11.4) (Not a function)
  595. //       "Maximum bipartite matching with 2‑SAT" → Sometimes the matching
  596. //       must satisfy additional logical constraints. You can first solve
  597. //       the 2‑SAT to determine which edges are possible, then run
  598. //       Hopcroft‑Karp on the resulting graph.
  599.  
  600. // 11.5) (Not a function)
  601. //       "Counting the number of maximum matchings" – this is #P‑complete
  602. //       in general, but for small graphs you can use DP over subsets.
  603. //       For large graphs, you usually only need the size, not the count.
  604.  
  605. // 11.6) (Not a function)
  606. //       "Dulmage‑Mendelsohn decomposition" – a way to classify vertices
  607. //       based on the maximum matching. Used in problems that ask for
  608. //       "which edges are in all maximum matchings" or "which vertices
  609. //       are always matched". This is advanced but has appeared in some
  610. //       ACPC problems.
  611.  
  612. // 11.7) (Not a function)
  613. //       "Maximum matching in a convex bipartite graph" – if the adjacency
  614. //       of each left vertex is a contiguous interval, you can solve it
  615. //       greedily in O(E log V). This is a special case that sometimes
  616. //       appears in ECPC.
  617.  
  618. // ===================================================================
  619. // 12) Simple Kuhn Algorithm (for small graphs or when simplicity is preferred)
  620. //     O(VE) – use only if V <= 500 or so.
  621. // ===================================================================
  622.  
  623. // 12.1) Kuhn's algorithm (DFS‑based augmenting path)
  624. //       PURPOSE:
  625. //         Simpler to code than Hopcroft‑Karp, but slower.
  626. //         Use this when the graph is small (V <= 500) or when you need
  627. //         a quick prototype.
  628. //       HOW TO USE:
  629. //         1. Create: Kuhn kuhn(n_left, n_right);
  630. //         2. Add edges: kuhn.add_edge(u, v);
  631. //         3. Get answer: int match_size = kuhn.max_matching();
  632. //       TIME COMPLEXITY:
  633. //         O(VE) in the worst case.
  634. //       CONSTRAINTS:
  635. //         - Works for V up to a few hundred.
  636. //         - Graph must be bipartite.
  637. struct Kuhn {
  638.     int n_left, n_right;
  639.     vector<vector<int>> adj;
  640.     vector<int> matchR, seen;
  641.  
  642.     Kuhn(int nL, int nR) : n_left(nL), n_right(nR) {
  643.         adj.resize(nL);
  644.         matchR.assign(nR, -1);
  645.     }
  646.  
  647.     void add_edge(int u, int v) {
  648.         adj[u].push_back(v);
  649.     }
  650.  
  651.     bool dfs(int u) {
  652.         for (int v : adj[u]) {
  653.             if (seen[v]) continue;
  654.             seen[v] = 1;
  655.             if (matchR[v] == -1 || dfs(matchR[v])) {
  656.                 matchR[v] = u;
  657.                 return true;
  658.             }
  659.         }
  660.         return false;
  661.     }
  662.  
  663.     int max_matching() {
  664.         int matching = 0;
  665.         for (int u = 0; u < n_left; u++) {
  666.             seen.assign(n_right, 0);
  667.             if (dfs(u)) matching++;
  668.         }
  669.         return matching;
  670.     }
  671. };
  672.  
  673. // ===================================================================
  674. // 13) Maximum Matching in a Bipartite Graph with weights (Assignment Problem)
  675. //     For weighted bipartite matching, use the Hungarian Algorithm.
  676. //     This is NOT Hopcroft‑Karp (which is for unweighted graphs).
  677. //     See the Hungarian Algorithm template for that.
  678. // ===================================================================
  679.  
  680. // ===================================================================
  681. // main() with example usage (you can ignore this part)
  682. // ===================================================================
  683.  
  684. int main() {
  685.     ios::sync_with_stdio(false);
  686.     cin.tie(nullptr);
  687.  
  688.     // Example: maximum matching in a small graph
  689.     HopcroftKarp hk(3, 3);
  690.     hk.add_edge(0, 0);
  691.     hk.add_edge(0, 1);
  692.     hk.add_edge(1, 1);
  693.     hk.add_edge(2, 2);
  694.  
  695.     cout << "Maximum matching size: " << hk.max_matching() << '\n'; // 3
  696.  
  697.     // Example: minimum vertex cover
  698.     auto cover = min_vertex_cover(hk);
  699.     cout << "Vertex cover (left): ";
  700.     for (int u : cover.first) cout << u << " ";
  701.     cout << "\nVertex cover (right): ";
  702.     for (int v : cover.second) cout << v << " ";
  703.     cout << '\n';
  704.  
  705.     // Example: maximum independent set
  706.     auto indep = max_independent_set(hk);
  707.     cout << "Independent set (left): ";
  708.     for (int u : indep.first) cout << u << " ";
  709.     cout << "\nIndependent set (right): ";
  710.     for (int v : indep.second) cout << v << " ";
  711.     cout << '\n';
  712.  
  713.     return 0;
  714. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Maximum matching size: 3
Vertex cover (left): 0 1 2 
Vertex cover (right): 
Independent set (left): 
Independent set (right): 0 1 2
https://ideone.com/EsZh4L
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!