Cod sursa(job #2872227)

Utilizator BorodiBorodi Bogdan Borodi Data 16 martie 2022 16:31:48
Problema Felinare Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <cstring>
#define Nmax 8191
using namespace std;

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

typedef vector <int> VI;
int n, m, St[Nmax], Dr[Nmax], x, y;

struct drum{
    int x, y;
}D[20001];

bool E[Nmax];
VI V[Nmax];

int cuplaj(int vertex){
    E[vertex] = 1;

    for(int new_vertex : V[vertex])
        if(!Dr[new_vertex] && E[new_vertex] == 0){
            St[vertex] = new_vertex;
            Dr[new_vertex] = vertex;

            return 1;
        }

    for(int new_vertex : V[vertex])
        if(cuplaj(new_vertex) && E[new_vertex] == 0){
            St[vertex] = new_vertex;
            Dr[new_vertex] = vertex;
            return 1;
        }

    return 0;
}

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

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

    int done = 0, cnt = 0;

    while(!done){
        done = 1;

        memset(E, 0, sizeof(E));

        for(int i = 1; i <= n; ++i)
            if(St[i] == 0 && cuplaj(i)){
                done = 0;
                cnt++;
            }
    }

    fout << (n * 2) - cnt << "\n";

    for(int i = 1; i <= m; ++i){
        x = D[i].x;
        y = D[i].y;

        if(St[x] == y && Dr[y] == x)
            fout << 2 << '\n';
        else fout << 3 << "\n";
    }

    return 0;
}