Cod sursa(job #1967494)

Utilizator bt.panteaPantea Beniamin bt.pantea Data 16 aprilie 2017 18:49:56
Problema Felinare Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <cstring>
#define NMAX 8192
using namespace std;
ifstream f ("felinare.in");
ofstream g ("felinare.out");
int n, m, cnt, l[NMAX], r[NMAX], sl[NMAX], sr[NMAX], u[NMAX];
vector < int > a[NMAX];
inline void Read() {
    f>>n>>m;
    while(m--) {
        int x, y;
        f>>x>>y;
        a[x].push_back(y);
    }
}
inline int pairup(const int & nod) {
    if(u[nod])
        return 0;
    u[nod] = 1;
    for (int i = 0; i < a[nod].size(); i++) {
        int next = a[nod][i];
        if (!l[next]) {
            l[next] = nod;
            r[nod] = next;
            sl[nod] = 1;
            return 1;
        }
    }
    for (int i = 0; i < a[nod].size(); i++) {
        int next = a[nod][i];
        if (pairup(l[next]))  {
            l[next] = nod;
            r[nod] = next;
            sl[nod] = 1;
            return 1;
        }
    }
    return 0;
}
inline void support(const int & nod) {
    for (int i = 0; i < a[nod].size(); i++) {
        int next = a[nod][i];
        if (!sr[next]) {
            sr[next] = 1;
            sl[l[next]] = 0;
            support(l[next]);
        }
    }
}
inline void Solve() {
    cnt = 0;
    for (int i = 1; i <= n; i++)
        if (!pairup(i)) {
            memset(u, 0, sizeof(u));
            cnt += pairup(i);
        } else cnt++;
    /* for (int i = 1; i <= n; i++) {
        if (!sl[i])
            support(i);
    } */
}
int main()
{
    Read();
    Solve();
    g<<2 * n - cnt;
    return 0;
}