Cod sursa(job #1360790)

Utilizator danalex97Dan H Alexandru danalex97 Data 25 februarie 2015 17:54:12
Problema Cuplaj maxim in graf bipartit Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

const int N = 10010;

ifstream F("cuplaj.in");
ofstream G("cuplaj.out");

int n,m,e,p1[N],p2[N],mk[N];
vector<int> v[N];

int can(int y)
{
    if ( mk[ p2[y] ] ) return 0;
    if ( p2[y] == 0 ) return 1;

    int x = p2[y];
    mk[x] = 1;

    for (int i=0;i<int(v[x].size());++i)
    {
        int y2 = v[x][i];
        if ( y2 != y )
            if ( can(y2) )
            {
                p1[x] = y2;
                p2[y2] = x;
                return 1;
            }
    }
    return 0;
}

int main()
{
    F>>n>>m>>e;
    for (int i=1,x,y;i<=e;++i)
    {
        F>>x>>y;
        v[x].push_back(y);
    }

    int co = 0;
    int lst = -1;
    while ( co != lst )
    {
        lst = co;
        for (int x=1;x<=n;++x)
            if ( p1[x] == 0 )
            {
                //memset(mk,0,sizeof(mk));
                for (int j=0;j<int(v[x].size());++j)
                {
                    int y = v[x][j];
                    if ( can(y) )
                    {
                        p1[x] = y;
                        p2[y] = x;
                        ++co;
                        break;
                    }
                }
            }
        memset(mk,0,sizeof(mk));
    }
    G<<co<<'\n';
    for (int i=1;i<=n;++i)
        if ( p1[i] )
            G<<i<<' '<<p1[i]<<'\n';
}