Maksymalne Skojarzenie W Grafie Dwudzielnym

/*
* autor: Piotr Kraska
* data: 15 - 01 - 09
*/
 
#include <iostream>
#include <vector>
#include <deque>
 
using namespace std;
 
const int NIES = 1000000000;
 
vector<vector<int> > graf;
 
deque<int> kolejka;
vector<int> poziom;
vector<int> ojciec;
vector<int> skojarzony_z;
 
void skojarzenie_maksymalne ()
{
    int v, u, ostatni;
 
    kolejka.clear();
    poziom.resize(graf.size());
    ojciec.resize(graf.size());
    skojarzony_z.assign(graf.size(), NIES);
 
    for (int i = 0 ; i < (int)graf.size() ; ++i)
    {
        // Jeśli wierzchołek jest już skojarzony pomijamy go
        if (skojarzony_z[i] != NIES) continue;
 
        fill(poziom.begin(), poziom.end(), 0);
        fill(ojciec.begin(), ojciec.end(), NIES);
 
        poziom[i] = 1;
        kolejka.clear();
        kolejka.push_back(i);
 
        // Ostatni to wierzchołek powiększający skojarzenie
        ostatni = NIES;
 
        while (!kolejka.empty() && ostatni == NIES)
        {
            v = kolejka.front();
            kolejka.pop_front();
 
            if (poziom[v] & 1) // poziom[v] jest nieparzysty
            {
                for (vector<int>::const_iterator j = graf[v].begin() ; j != graf[v].end() ; ++j)
                {
                    u = *j;
 
                    // Jeśli wierzchołek ma poziom inny niż zero pomijamy go
                    if (poziom[u] != 0) continue;
 
                    if (skojarzony_z[u] == NIES) // u jest nieskojarzony
                    {
                        ojciec[u] = v;
                        ostatni = u;
                        break;
                    }
                    else
                    if (skojarzony_z[u] != v) // u skojarzony, ale nie z v
                    {
                        poziom[u] = poziom[v] + 1;
                        ojciec[u] = v;
                        kolejka.push_back(u);
                    }
                }
            }
            else // poziom[v] jest parzysty
            {
                poziom[skojarzony_z[v]] = poziom[v] + 1;
                ojciec[skojarzony_z[v]] = v;
                kolejka.push_back(skojarzony_z[v]);
            }
        }
 
        // Jeśli znaleziono ścieżkę powiększającą, to ją ustawiamy
        if (ostatni != NIES)
        {
            for (int j = ostatni ; j != NIES ; j = ojciec[ojciec[j]])
            {
                skojarzony_z[j] = ojciec[j];
                skojarzony_z[ojciec[j]] = j;
            }
        }
    }
}
 
void test ()
{
    /*
    * Wierzchołki numerowane od zera!
    * n - ilość wierzhołków
    * m - ilość krawędzi
    */
    int n, m, a, b;
 
    cin >> n >> m;
 
    graf.resize(n);
 
    for (int i = 0 ; i < m ; ++i)
    {
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a); // Skomentuj tą linię dla grafu skierowanego
    }
 
    skojarzenie_maksymalne();
 
    for (int i = 0 ; i < n ; ++i)
    {
        cout << "Wierzcholek " << i << endl;
        cout << "Skojarzony z " << skojarzony_z[i] << endl << endl;
    }
}
 
int main ()
{
    test();
 
    return 0;
}