Cod sursa(job #2458754)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 21 septembrie 2019 13:53:34
Problema Felinare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("felinare.in");
ofstream fout("felinare.out");

int n, m, l[10005], r[10005], ans;
bool check[10005], sr[10005], sl[10005];
vector <int> v[10005];

void support(int nod)
{

    for(int i = 0; i < v[nod].size(); i++)
    {
        int child = v[nod][i];

        if(!sr[child])
        {
            sr[child] = 1;
            sl[l[child]] = 0;
            support(l[child]);
        }
    }
}
bool cuplaj(int nod)
{
    if(check[nod]) return false;

    check[nod] = true;

    for(int i = 0; i < v[nod].size(); i++)
    {
        int child = v[nod][i];
        if(!l[child])
        {
            l[child] = nod;
            r[nod] = child;
            return true;
        }
    }

    for(int i = 0; i <  v[nod].size(); i++)
    {
        int child = v[nod][i];
        if(cuplaj(l[child]))
        {
            l[child] = nod;
            r[nod] = child;
            return true;
        }
    }

    return false;
}

int main()
{

    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;

        v[a].push_back(b);
    }

    bool ok = true;
    while(ok)
    {
        ok = 0;
        for(int i = 1; i <= n; i++)
            ok |= cuplaj(i);
    }
    for(int i = 1; i <= n; i ++)
        if(r[i])
            ans++;
    fout << 2*n-ans << '\n';
    for(int i = 1; i <= n; i++)
    {
        if(r[i])
            sl[i] = 1;
    }
    for(int i = 1; i <= n; i++)
        if(!r[i])
            support(i);
    for(int i = 1; i <= n; i ++)
    {
        if(sl[i] && sr[i])
            fout << 0 << '\n';
        else
            if(sl[i]) fout << 2 << '\n';
            else
                if(sr[i]) fout << 1 << '\n';
            else
                fout << 3 << '\n';
    }
    return 0;
}