fork download
copy 
  1. /*
  2.   Copyright 2012 Marek "p2004a" Rusinowski
  3.   Edmonds's matching algorithm O(mn)
  4. */
  5. #include <cstdio>
  6. #include <vector>
  7. #include <algorithm>
  8.  
  9. using namespace std;
  10.  
  11. const int max_n = 10000;
  12.  
  13. vector<int> edges[max_n * 2], /* graph */
  14.  contains[max_n * 2]; /* for every pseudonode contains list of cycle nodes */
  15. int n, m, num_cycles = 0, match[max_n * 2],
  16.  d[max_n * 2], /* distance from node to tree root, we care only if it's even */
  17.  f[max_n * 2], /* root of tree that contains node */
  18.  a[max_n * 2]; /* ancestor of node in tree, correct for nodes with odd dist */
  19. bool act[max_n * 2]; /* determines if node is active */
  20. long long time = 0, t[max_n * 2];
  21.  
  22. void build_alternating_tree(int father, int dist = 0, int v = -1) {
  23.   if (v == -1) v = father;
  24.   d[v] = dist;
  25.   f[v] = father;
  26.   for (int i = 0; i < (int)edges[v].size(); ++i) {
  27.     if (d[edges[v][i]] == -1 && match[edges[v][i]] != -1) {
  28.       d[edges[v][i]] = dist + 1;
  29.       f[edges[v][i]] = father;
  30.       a[edges[v][i]] = v;
  31.       build_alternating_tree(father, dist + 2, match[edges[v][i]]);
  32.     }
  33.   }
  34. }
  35.  
  36. void build_alternating_forest() {
  37.   /* delete old forest */
  38.   fill(d, d + n + num_cycles, -1);
  39.  
  40.   /* build new forest, we start building tree from unmatched vertex */
  41.   for (int i = 0; i < n + num_cycles; ++i) {
  42.     if (match[i] == -1) {
  43.       build_alternating_tree(i);
  44.     }
  45.   }
  46. }
  47.  
  48. void add_neighbours_from_to(int u, int v) {
  49.   for (int i = 0; i < (int) edges[u].size(); ++i) {
  50.     if (act[edges[u][i]]) {
  51.       edges[edges[u][i]].push_back(v);
  52.       edges[v].push_back(edges[u][i]);
  53.  
  54.       /* We must remember about this if because without it we would had to 
  55.       rebuild whole M-alternating tree after finding cycle. */
  56.       if (a[edges[u][i]] == u) {
  57.         a[edges[u][i]] = v;
  58.       }
  59.     }
  60.   }
  61. }
  62.  
  63. inline void cycle_build_helper(int &v, vector<int> &in) {
  64.   act[v] = false;
  65.   in.push_back(v);
  66.   act[match[v]] = false;
  67.   in.push_back(match[v]);
  68.   v = a[match[v]];
  69. }
  70.  
  71. void lca_helper(int &v, bool &path_v_end, bool &v_hit, long long time_begin) {
  72.   if (!path_v_end) {
  73.     if (t[v] < time_begin) {
  74.       t[v] = time;
  75.     } else {
  76.       v_hit = true;
  77.       return;
  78.     }
  79.     if (match[v] != -1) {
  80.       v = a[match[v]];
  81.     } else {
  82.       path_v_end = true;
  83.     }
  84.   }
  85. }
  86.  
  87. void contract_cycle(int v, int u) {
  88.   /* If we haven't much time we can implement finding cycle nodes as pushing
  89.   all nodes from u->root and v->root to two vectors and then pop_backs from them
  90.   until last elements exists and are equal. The computional complexity will
  91.   increase to about O(n^4) using this technique. */
  92.   int cycle_v = n + num_cycles++;
  93.   long long time_begin = ++time;
  94.  
  95.   /* find lca */
  96.   int new_v = v, new_u = u, shift;
  97.   bool path_v_end = false, path_u_end = false, v_hit = false, u_hit = false;
  98.  
  99.   while (!v_hit && !u_hit) {
  100.     lca_helper(new_v, path_v_end, v_hit, time_begin);
  101.     lca_helper(new_u, path_u_end, u_hit, time_begin);
  102.     ++time;
  103.   }
  104.   shift = time - t[v_hit ? new_v : new_u] - 1;
  105.  
  106.   /* align nodes to the same level in tree using shift computed with lca */
  107.   vector<int> p;
  108.   while(shift--) {
  109.     cycle_build_helper(v_hit ? v : u, v_hit ? contains[cycle_v] : p);
  110.   }
  111.  
  112.   /* build rest of cycle */
  113.   while (v != u) {
  114.     cycle_build_helper(v, contains[cycle_v]);
  115.     cycle_build_helper(u, p);
  116.   }
  117.   contains[cycle_v].insert(contains[cycle_v].end(), p.rbegin(), p.rend());
  118.   act[v] = false;
  119.   contains[cycle_v].push_back(v);
  120.  
  121.   /* add to created pseudonode edges from cycle neighbours */
  122.   for (int j = 0; j < (int)contains[cycle_v].size(); ++j) {
  123.     add_neighbours_from_to(contains[cycle_v][j], cycle_v);
  124.   }
  125.  
  126.   if (d[v] > 0) {
  127.     match[match[v]] = cycle_v;
  128.     match[cycle_v] = match[v];
  129.   } else {
  130.     match[cycle_v] = -1;
  131.   }
  132.  
  133.   d[cycle_v] = d[v];
  134.   f[cycle_v] = f[v];
  135.   act[cycle_v] = true;
  136. }
  137.  
  138. void reverse_match_to_root(int v, int old = -1) {
  139.   if (d[v] != 0) {
  140.     match[match[v]] = a[match[v]];
  141.     reverse_match_to_root(a[match[v]], match[v]);
  142.   }
  143.   match[v] = old;
  144. }
  145.  
  146. inline bool check_node(int i) {
  147.   return act[i] && d[i] % 2 == 0;
  148. }
  149.  
  150. bool find_path() {
  151.   for (int i = 0; i < n + num_cycles; ++i) {
  152.     if (check_node(i)) {
  153.       for (int j = 0; j < (int) edges[i].size(); ++j) {
  154.         if (check_node(edges[i][j])) {
  155.           if (f[i] == f[edges[i][j]]) {
  156.             contract_cycle(i, edges[i][j]);            
  157.             return find_path();
  158.           } else {
  159.             reverse_match_to_root(i);
  160.             reverse_match_to_root(edges[i][j]);
  161.             match[i] = edges[i][j];
  162.             match[edges[i][j]] = i;
  163.             return true;
  164.           }
  165.         }
  166.       }
  167.     }
  168.   }
  169.   return false;
  170. }
  171.  
  172. void expand_cycles() {
  173.   while (num_cycles--) {
  174.     int u, pos = 0, cycle_size = contains[num_cycles + n].size(),
  175.      cycle_v = num_cycles + n;
  176.     for (int i = 0; i < cycle_size; ++i) {
  177.       u = contains[cycle_v][i];
  178.  
  179.       /* delete from cycle's neighbours pseudonode representing cycle */
  180.       for (int j = 0; j < (int) edges[u].size(); ++j) {
  181.         if (act[edges[u][j]]) {
  182.           if (edges[u][j] == match[cycle_v]) {
  183.             pos = i;
  184.           }
  185.           edges[edges[u][j]].pop_back();
  186.         }
  187.       }
  188.     }
  189.  
  190.     for (int i = 0; i < cycle_size; ++i) {
  191.       act[contains[cycle_v][i]] = true;
  192.     }
  193.  
  194.     u = contains[cycle_v][pos];
  195.     match[u] = match[cycle_v];
  196.     match[match[u]] = u;
  197.  
  198.     /* build correct match on cycle */
  199.     for (int i = pos + 1; i < cycle_size + pos; i += 2) {
  200.       match[contains[cycle_v][i % cycle_size]] = 
  201.        contains[cycle_v][(i + 1) % cycle_size];
  202.       match[contains[cycle_v][(i + 1) % cycle_size]] = 
  203.        contains[cycle_v][i % cycle_size];
  204.     }
  205.  
  206.     contains[cycle_v].clear();
  207.     edges[cycle_v].clear();
  208.   }
  209.   num_cycles = 0;
  210. }
  211.  
  212. class degree_cmp {
  213.  public:
  214.   bool operator() (int b, int c) {
  215.     return edges[b].size() < edges[c].size();
  216.   }
  217. } degree_comp;
  218.  
  219. /* creating match by trying to match nodes with smallest degree first */
  220. void create_random_match() {
  221.   vector<int>nodes;
  222.   for (int i = 0; i < n; ++i) {
  223.     nodes.push_back(i);
  224.   }
  225.   sort(nodes.begin(), nodes.end(), degree_comp);
  226.   for (int i = 0; i < n; ++i) {
  227.     if (match[nodes[i]] == -1) {
  228.       int min_degree = 1000000, v = -1;
  229.       for (int j = 0; j < (int)edges[nodes[i]].size(); ++j) {
  230.         if (match[edges[nodes[i]][j]] == -1 && 
  231.          (int)edges[edges[nodes[i]][j]].size() < min_degree) {
  232.           min_degree = edges[edges[nodes[i]][j]].size();
  233.           v = edges[nodes[i]][j];
  234.         }
  235.       }
  236.       if (v >= 0) {
  237.         match[nodes[i]] = v;
  238.         match[v] = nodes[i];
  239.       }
  240.     }
  241.   }
  242. }
  243.  
  244. int main() {
  245.   int b, c;
  246.   scanf("%d %d", &n, &m);
  247.   for (int i = 0; i < m; ++i) {
  248.     scanf("%d %d", &b, &c);
  249.     edges[--b].push_back(--c);
  250.     edges[c].push_back(b);
  251.   }
  252.  
  253.   fill(act, act + n, true);
  254.   fill(match, match + n, -1);
  255.  
  256.   create_random_match();
  257.  
  258.   do {
  259.     expand_cycles();
  260.     build_alternating_forest();
  261.   } while (find_path());
  262.  
  263.   /* printing output */
  264.   vector<pair<int, int> > out;
  265.   for (int i = 0; i < n; ++i) {
  266.     if (match[i] > i) {
  267.       out.push_back(make_pair(i, match[i]));
  268.     }
  269.   }
  270.   printf("%d\n", out.size());
  271.   for (int i = 0; i < (int)out.size(); ++i) {
  272.     printf("%d %d\n", out[i].first + 1, out[i].second + 1);
  273.   }
  274.   return 0;
  275. }
  276.  
Success #stdin #stdout 0.01s 3780KB
comments (?)
stdin
copy 
6 7
1 2
1 3
2 4
2 5
2 6
3 4
4 5
stdout
copy 
3
1 3
2 6
4 5
https://ideone.com/EQUcH
Edmond's matching
language:
C++ (gcc 8.3)
created:
12 years 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!