Cod sursa(job #2510709)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 17 decembrie 2019 10:44:44
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <vector>

#define N 100000 + 1

using namespace std;

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

vector < int > graph[N];
int lvl, vsol[N], sol[N], niv[N], low[N], st[N], k, num, critic[N];
bool stiva[N];

void dfs ( int node ){
    niv[node] = low[node] = ++lvl;
    st[++k] = node;
    stiva[node] = 1;
    for ( int i = 0; i < graph[node].size ( ); i++ ){
        int new_node = graph[node][i];
        if ( niv[new_node] == 0 ){
            dfs ( new_node );
            low[node] = min ( low[node], low[new_node] );
            if ( niv[node] <= low[new_node] )
                critic[node] = new_node;
        }
        else if ( stiva[new_node] == 1 )
            low[node] = min ( low[node], niv[new_node] );
    }
    if ( critic[node] != 0 ){
        num++;
        sol[num] = sol[num - 1] + 1;
        vsol[sol[num]] = node;
        while ( st[k] != critic[node] ){
            vsol[++sol[num]] = st[k];
            stiva[st[k]] = 0;
            k--;
        }
        vsol[++sol[num]] = st[k];
        stiva[st[k]] = 0;
        k--;
    }
}

int main()
{   int n, m, i, x, y;
    f >> n >> m;
    for ( i = 1; i <= m; i++ ){
        f >> x >> y;
        graph[x].push_back ( y );
        graph[y].push_back ( x );
    }
    for ( i = 1; i <= n; i++ )
        if ( niv[i] == 0 )
            dfs ( i );
    if ( k != 0 ){
        num++;
        sol[num] = sol[num - 1];
        while ( k > 0 ){
            vsol[++sol[num]] = st[k];
            k--;
        }
    }
    g << num << '\n';
    for ( i = 1; i <= num; i++ ){
        for ( int j = sol[i - 1] + 1; j <= sol[i]; j++ )
            g << vsol[j] << ' ';
        g << '\n';
    }
    return 0;
}