fork(8) download
copy 
  1. /*
  2.   Copyright 2011 Marek "p2004a" Rusinowski
  3.   Turbo matching algorithm
  4. */
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <vector>
  8.  
  9. #define MAXN 10000
  10.  
  11. std::vector<int> edges[MAXN];
  12. int part[MAXN], match[MAXN], n, m;
  13. bool visited[MAXN];
  14.  
  15. bool create_bipartite_graph(int v, int type) {
  16.   part[v] = type;
  17.   for (unsigned i = 0; i < edges[v].size(); ++i) {
  18.     if (part[edges[v][i]] != (type ^ 3)) {
  19.       if (part[edges[v][i]] == type || !create_bipartite_graph(edges[v][i], type ^ 3)) {
  20.         return false;
  21.       }
  22.     }
  23.   }
  24.   return true;
  25. }
  26.  
  27. bool dfs(int v) {
  28.   visited[v] = true;
  29.   for (unsigned i = 0; i < edges[v].size(); ++i) {
  30.     if (!visited[edges[v][i]] && (!~match[edges[v][i]] || (visited[edges[v][i]] = true, dfs(match[edges[v][i]])))) {
  31.       match[v] = edges[v][i];
  32.       match[edges[v][i]] = v;
  33.       return true;
  34.     }
  35.   }
  36.   return false;
  37. }
  38.  
  39. void turbo_matching() {
  40.   bool con = true;
  41.   while (con) {
  42.     con = false;
  43.     memset(visited, 0x00, sizeof(bool) * n);
  44.     for (int i = 0; i < n; ++i) {
  45.       if (part[i] & 1 && !visited[i] && !~match[i]) {
  46.         con |= dfs(i);
  47.       }
  48.     }
  49.   }
  50. }
  51.  
  52. int main() {
  53.   int a, b;
  54.   scanf("%d %d", &n, &m);
  55.   for (int i = 0; i < m; ++i) {
  56.     scanf("%d %d", &a, &b);
  57.     edges[--a].push_back(--b);
  58.     edges[b].push_back(a);
  59.   }
  60.   if (!create_bipartite_graph(0, 1)) {
  61.     printf("false\n");
  62.     return 0;
  63.   }
  64.   memset(match, 0xFF, sizeof(int) * n);
  65.   turbo_matching();
  66.   for (int i = 0; i < n; ++i) {
  67.     if (~match[i]) {
  68.       printf("%d %d\n", i + 1, match[i] + 1);
  69.       match[match[i]] = -1;
  70.     }
  71.   }
  72.   return 0;
  73. }
  74.  
stdin
copy 
7 8
1 7
1 6
1 5
2 6
2 5
2 4
3 5
3 4
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:54: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
stdout
copy 
1 7
2 6
3 5
https://ideone.com/J6VRD
Turbo matching
language:
C++ (gcc 8.3)
created:
13 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!