Cod sursa(job #2872133)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 16 martie 2022 12:47:24
Problema Felinare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#include <vector>
#include <cstring>
#define NMAX 8191

using namespace std;

ifstream f("felinare.in");
ofstream g("felinare.out");

int n, m;

vector < int > adj[NMAX + 1];

int l[NMAX + 1], r[NMAX + 1];

bool used[NMAX + 1];

pair < bool, bool > inSuport[NMAX + 1];

bool pairup(int node)
{
    if (used[node])
        return false;

    used[node] = true;

    for (auto it : adj[node])
        if (!r[it])
        {
            l[node] = it;
            r[it] = node;
            return true;
        }

    for (auto it : adj[node])
        if (pairup(r[it]))
        {
            l[node] = it;
            r[it] = node;
            return true;
        }

    return false;
}

void calc(int node)
{
    for (auto it : adj[node])
        if (!inSuport[it].second)
        {
            inSuport[it].second = true;
            inSuport[r[it]].second = false;
            calc(r[it]);
        }
}

int main()
{
    f >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int x, y; f >> x >> y;
        adj[x].push_back(y);
    }

    while (true)
    {
        memset(used, false, sizeof(used));

        bool ok = false;

        for (int i = 1; i <= n; i++)
            ok = ok | pairup(i);

        if (!ok)
            break;
    }

    for (int i = 1; i <= n; i++)
        if (l[i])
            inSuport[i].first = true;

    for (int i = 1; i <= n; i++)
        if (!l[i])
            calc(i);

    for (int i = 1; i <= n; i++)
        if (!inSuport[i].first)
            calc(i);

    int nrFelinare = 0;

    for (int i = 1; i <= n; i++)
    {
        if (!inSuport[i].first)
            nrFelinare++;

        if (!inSuport[i].second)
            nrFelinare++;
    }

    g << nrFelinare << "\n";
    for (int i = 1; i <= n; i++)
    {
        if (!inSuport[i].first && !inSuport[i].second)
            g << 3 << "\n";
        else if (!inSuport[i].first)
            g << 1 << "\n";
        else if (!inSuport[i].second)
            g << 2 << "\n";
        else
            g << 0 << "\n";
    }

    return 0;
}