Cod sursa(job #2988204)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 3 martie 2023 19:51:42
Problema Felinare Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;

ifstream cin( "felinare.in" );
ofstream cout( "felinare.out" );

const int MAX = 8193;

vector<int> v[ MAX ];
bitset<MAX> cuplat;
bitset<MAX> viz;

int low[ MAX ];
int t[ MAX ];
int n, m;

int cuplaj( const int& nod ) {
    if( viz[ nod ] ) 
        return 0;

    viz[ nod ] = 1;
    for( const int& X : v[ nod ] )
        if( !t[ X ] ) {
            cuplat[ nod ] = 1;
            low[ nod ] = X;
            t[ X ] = nod;
            return 1;
        }

    for( const int& X : v[ nod ] )
        if( cuplaj( t[ X ] ) ) {
            cuplat[ nod ] = 1;
            low[ nod ] = X;
            t[ X ] = nod;
            return 1;
        }
    return 0;
}

void calc( const int& nod ) {
    for( const int& X : v[ nod ] )
        if( !viz[ X ] ) {
            cuplat[ t[ X ] ] = 0;
            viz[ X ] = 1;

            calc( t[ X ] );
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    int k = 0;
    for( int i = 1; i <= n; i++ )
        if( !low[ i ] && cuplaj( i ) ) {
            viz = 0;
            k++;
        }

    viz = 0;
    cout << 2 * n - k << "\n";
    for( int i = 1; i <= n; i++ )
        if( !cuplat[ i ] )
          calc( i );

    for( int i = 1, rez = 3; i <= n; i++, rez = 3 ) {
        if( viz[ i ] ) 
            rez -= 2;
        rez -= ( cuplat[ i ] );
        cout << rez << "\n";
    }
    return 0;
}