Maximum Bipartite Matching
#include <iostream>
#include <vector>
 
#define MAX 10000 // max(|A|,|B|)
 
using namespace std;
 
#define INPUT_FILE "input.in"
#define OUTPUT_FILE "input.out"
 
int M[MAX] = {0};                          // B--A |M| = |B|
int V[MAX] = {0};
vector< vector<int> > W(MAX);        // A--B
 
int k;
 
int dfs( int b ) 
{
    if( V[b] != k ) 
    {
        V[b] = k;
        for( int j = 0; j < W[b].size(); j++ ) 
        {
            if( M[ W[b][j] ] == 0 || dfs( M[ W[b][j] ] ) ) 
            {
                M[ W[b][j] ] = b;
                return 1;
            }
        }
    }
    return 0;
}
 
int main()
{
#ifdef ALEX
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    freopen(INPUT_FILE, "r", stdin);
    freopen(OUTPUT_FILE, "w", stdout);
#endif
 
    int n, m;
 
    // n = |A|
    // m = |B|
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        while (a != 0)
        {
            W[i].push_back(a);
            cin >> a;
        }
    }
 
    for(k = 1; k <= n; k++) 
        dfs(k);
 
    int res = 0;
    for(int i = 1; i <= m; i++) res+= (M[i] != 0)?1:0;
 
    for(int i = 1; i <= m; i++) 
    {
        if( M[i] != 0 ) 
        {
            printf("%d %d\n", M[i], i);  // A--B
        }
    }
 
    return 0;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.