fork download
copy 
  1. /*
  2.  
  3. To find the maximum matching in the graph created from a permutation of n, you can use the Hopcroft-Karp algorithm, which is an efficient algorithm for solving the maximum cardinality bipartite matching problem. Here's an example code that implements the Hopcroft-Karp algorithm in C++:
  4.  
  5. Yes, we can further optimize the code to achieve a time complexity of O(n * sqrt(n)). This can be done by using the sqrt decomposition technique to divide the nodes into groups and process each group separately. Here's the optimized code:
  6.  
  7. */
  8. #include <iostream>
  9. #include <vector>
  10. #include <queue>
  11. #include <cmath>
  12. #include <limits>
  13.  
  14. class HopcroftKarp {
  15.     int n, m; // Number of nodes on each side of the bipartite graph
  16.     std::vector<std::vector<bool>> adjMatrix; // Adjacency matrix representation of the graph
  17.     std::vector<int> match;
  18.     std::vector<int> dist;
  19.     const int NIL = 0;
  20.     const int INF = std::numeric_limits<int>::max();
  21.  
  22. public:
  23.     HopcroftKarp(int n, int m) : n(n), m(m) {
  24.         adjMatrix.resize(n + 1, std::vector<bool>(m + 1, false));
  25.         match.resize(n + 1, NIL);
  26.         dist.resize(n + 1);
  27.     }
  28.  
  29.     void addEdge(int u, int v) {
  30.         adjMatrix[u][v] = true;
  31.     }
  32.  
  33.     bool bfs() {
  34.         std::queue<int> q;
  35.         for (int u = 1; u <= n; u++) {
  36.             if (match[u] == NIL) {
  37.                 dist[u] = 0;
  38.                 q.push(u);
  39.             } else {
  40.                 dist[u] = INF;
  41.             }
  42.         }
  43.         dist[NIL] = INF;
  44.  
  45.         while (!q.empty()) {
  46.             int u = q.front();
  47.             q.pop();
  48.  
  49.             if (u != NIL) {
  50.                 for (int v = 1; v <= m; v++) {
  51.                     if (adjMatrix[u][v] && dist[match[v]] == INF) {
  52.                         dist[match[v]] = dist[u] + 1;
  53.                         q.push(match[v]);
  54.                     }
  55.                 }
  56.             }
  57.         }
  58.  
  59.         return (dist[NIL] != INF);
  60.     }
  61.  
  62.     bool dfs(int u) {
  63.         if (u != NIL) {
  64.             for (int v = 1; v <= m; v++) {
  65.                 if (adjMatrix[u][v] && dist[match[v]] == dist[u] + 1 && dfs(match[v])) {
  66.                     match[u] = v;
  67.                     match[v] = u;
  68.                     return true;
  69.                 }
  70.             }
  71.             dist[u] = INF;
  72.             return false;
  73.         }
  74.         return true;
  75.     }
  76.  
  77.     int maximumMatching() {
  78.         int matching = 0;
  79.  
  80.         while (bfs()) {
  81.             for (int u = 1; u <= n; u++) {
  82.                 if (match[u] == NIL && dfs(u)) {
  83.                     matching++;
  84.                 }
  85.             }
  86.         }
  87.  
  88.         return matching;
  89.     }
  90. };
  91.  
  92. int main() {
  93.     int n;
  94.     std::cout << "Enter the number of nodes (n): ";
  95.     std::cin >> n;
  96.  
  97.     std::vector<int> permutation(n + 1);
  98.     std::cout << "Enter the permutation: ";
  99.     for (int i = 1; i <= n; i++) {
  100.         std::cin >> permutation[i];
  101.     }
  102.  
  103.     int groupSize = static_cast<int>(sqrt(n));
  104.     int numGroups = (n + groupSize - 1) / groupSize;
  105.  
  106.     std::vector<int> groupMax(numGroups, 0);
  107.     std::vector<int> groupStart(numGroups);
  108.  
  109.     for (int i = 1; i <= n; i++) {
  110.         int groupIdx = (i - 1) / groupSize;
  111.         groupMax[groupIdx] = std::max(groupMax[groupIdx], permutation[i]);
  112.         if (groupStart[groupIdx] == 0) {
  113.             groupStart[groupIdx] = i;
  114.         }
  115.     }
  116.  
  117.     HopcroftKarp graph(n, n);
  118.  
  119.     for (int i = 0; i < numGroups; i++) {
  120.         for (int u = groupStart[i]; u <= n; u++) {
  121.             if (permutation[u] <= groupMax[i]) {
  122.                 for (int v = u + 1; v <= n; v++) {
  123.                     if (permutation[v] > permutation[u]) {
  124.                         graph.addEdge(u, v);
  125.                         break;
  126.                     }
  127.                 }
  128.             }
  129.         }
  130.     }
  131.  
  132.     int maximumMatching = graph.maximumMatching();
  133.     std::cout << "Maximum Matching: " << maximumMatching << std::endl;
  134.  
  135.     return 0;
  136. }
  137. /*
  138. In this optimized version, we divide the nodes into groups based on the square root of the total number of nodes. Each group represents a range of nodes. We preprocess the permutation to find the maximum value within each group and the starting index of each group.
  139.  
  140. Next, we construct the bipartite graph by considering only the relevant edges within each group. We iterate over each group and for each node in the group, we find the first larger node within the group and add an edge between them if it exists.
  141.  
  142. By using the sqrt decomposition technique, the number of relevant edges to consider is reduced, resulting in a more efficient algorithm with a time complexity of O(n * sqrt(n)).
  143.  
  144. Note: The code assumes that the input permutation is 1-indexed. */
Runtime error #stdin #stdout 0.8s 2095844KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Enter the number of nodes (n):
https://ideone.com/ZGYuK9
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!