Раздел «Алгоритмы».BipartiteMatchingCPP:

Максимальное паросочетание: реализация на C++

#include <cstdio>
#include <vector>
#define MAX 10001
using namespace std;

vector<int> G2B( MAX, 0 );       // G2B[g] — мальчик, который назначен девочке "g"
vector< vector<int> > W( MAX );  // W[b] — список смежных девочек мальчика "b"

int k;  // мальчик, начиная с которого мы ищем улучшающий путь
        // и одновременно цвет, в который мы закрашиваем всех мальчиков, до которых
        // мы можем добраться из мальчика k.

vector<int> V(MAX, 0); // цвета вершин-мальчиков

int dfs( int b ) {
   // L("dfs %d\n", b);
    if( V[b] != k ) {
        V[b] = k;
        for( int j = 0; j < W[b].size(); j++ ) {
            if( G2B[ W[b][j] ] == 0 || dfs( G2B[ W[b][j] ] ) ) {
                G2B[ W[b][j] ] = b;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    int Ng, Nb;     // число девочек и число мальчиков
    int E;          // число рёбер
    int g, b, res;
    scanf("%d%d%d", &Ng, &Nb, &E);
    while(E--) {
        scanf("%d%d", &g, &b); // девочка "g" соединена ребром с мальчиком "b"
        W[b].push_back(g);
    }
   for(k = 1, res = 0; k <= Nb; k++) {
      res += dfs(k);
   }
    printf( "%d\n", res );
    for(g = 1; g <= Ng; g++) 
        if( G2B[g] != 0 ) 
            printf("%d %d\n", g, G2B[g]);
    return 0;
}
AlgorithmClasifyForm
Type: Код
Scope: Графы
Strategy: Жадность
Language:  
Complexity: Medium