fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. vector< pair<int,int> >
  7. find_maximum_matching(
  8.         int A,
  9.         int B,
  10.         const vector< pair<int,int> > &edge_list)
  11. {
  12.     vector< vector<int> > BA;
  13.     BA.resize(B);
  14.     for (const auto &e : edge_list) BA[ e.second ].push_back( e.first );
  15.     vector<int> match(A,-1);
  16.     for (int b=0; b<B; ++b) {
  17.         vector<int> from(A,-1);
  18.         queue<int> Q;
  19.         for (int a : BA[b]) { Q.push(a); from[a]=a; }
  20.         while (!Q.empty()) {
  21.             int a = Q.front(); Q.pop();
  22.             if (match[a] == -1) {
  23.                 while (from[a] != a) { match[a] = match[from[a]]; a = from[a]; }
  24.                 match[a] = b;
  25.                 break;
  26.             } else {
  27.                 for (int x : BA[match[a]]) if (from[x]==-1) { Q.push(x); from[x]=a; }
  28.             }
  29.         }
  30.     }
  31.     vector< pair<int,int> > result;
  32.     for (int a=0; a<A; ++a) if (match[a] != -1) result.push_back( { a, match[a] } );
  33.     return result;
  34. }
  35.  
  36. int main() {
  37.     vector< pair<int,int> > edge_list = { {0,0}, {0,1}, {0,2}, {1,0}, {2,0} };
  38.     cout << find_maximum_matching(3, 3, edge_list).size() << endl;
  39. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/iGm8Dj
language:
C++14 (gcc 8.3)
created:
8 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!