Cod sursa(job #2822562)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 24 decembrie 2021 11:43:06
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.41 kb
#include <stdio.h>
#include <vector>
#include <stack>

#define MAX_N 100000
#define MAX_COMP MAX_N

using namespace std;

struct muchie {
    int u, v;

    bool operator == (const muchie &a) const {
        return u == a.u && v == a.v;
    }
    bool operator != (const muchie &a) const {
        return !(a == muchie{ u, v } || a == muchie{ v, u });
    }
};

int nrComp;
int viz[MAX_N + 1], dep[MAX_N + 1], climbDep[MAX_N + 1], inComp[MAX_N + 1];
stack <muchie> s;
vector <int> muchii[MAX_N + 1];
vector <int> sol[MAX_COMP];

void dfs( int u, int p ) {
    int v, i, j;
    muchie e;

    viz[u] = 1;
    climbDep[u] = dep[u] = dep[p] + 1;

    for ( i = 0; i < muchii[u].size(); i++ ) {
        v = muchii[u][i];
        if ( !viz[v] ) {
            s.push( { u, v } );
            dfs( v, u );
            if ( climbDep[v] < climbDep[u] )
                climbDep[u] = climbDep[v];

            if ( climbDep[v] >= dep[u] ) {
                do {
                    e = s.top();
                    s.pop();
                    if ( !inComp[e.u] ) {
                        inComp[e.u] = 1;
                        sol[nrComp].push_back( e.u );
                    }
                    if ( !inComp[e.v] ) {
                        inComp[e.v] = 1;
                        sol[nrComp].push_back( e.v );
                    }
                } while ( e != muchie{ u, v } );

                for ( j = 0; j < sol[nrComp].size(); j++ )
                    inComp[sol[nrComp][j]] = 0;
                nrComp++;
            }
        } else if ( v != p ) {
            if ( dep[v] < dep[u] ) {
                s.push( { u, v } );
                if ( dep[v] < climbDep[u] )
                    climbDep[u] = dep[v];
            }
        }
    }
}

int main() {
    FILE *fin, *fout;
    int n, m, u, v, i, j;

    fin = fopen( "biconex.in", "r" );
    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d", &u, &v );
        muchii[u].push_back( v );
        muchii[v].push_back( u );
    }
    fclose( fin );

    nrComp = 0;
    dfs( 1, 0 );

    fout = fopen( "biconex.out", "w" );
    fprintf( fout, "%d\n", nrComp );
    for ( i = 0; i < nrComp; i++ ) {
        for ( j = 0; j < sol[i].size(); j++ )
            fprintf( fout, "%d ", sol[i][j] );
        fprintf( fout, "\n" );
    }
    fclose( fout );

    return 0;
}