Cod sursa(job #3041974)

Utilizator Fantastic_Mantudor voicu Fantastic_Man Data 3 aprilie 2023 11:56:50
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
const int nmax = 1e5;

vector < int > g[nmax];
vector < int > c[nmax];
int comp = 0;
int vis[nmax];

struct time {
    int in;
    int low;
} info[nmax];

stack < int > st;

int T = 0;

void dfs ( int node, int par = -1 ) {
    vis[node] = 1;
    info[node].in = info[node].low = T++;
    st.push ( node );
    for ( int x: g[node] )
        if ( x != par ) {
            if ( vis[x] )
                info[node].low = min ( info[node].low, info[x].in );
            else {
                dfs ( x, node );
                info[node].low = min ( info[node].low, info[x].low );
                if ( info[x].low >= info[node].in ) {
                    while ( st.top () != x )
                        c[comp].push_back ( st.top () ), st.pop ();
                    c[comp].push_back ( x ); st.pop ();
                    c[comp].push_back ( node );
                    comp++;
                }
            }
        }
}

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

int main() {
    int n, m, x, y;
    fin >> n >> m;
    for ( int i = 0; i < m; i++ ) {
        fin >> x >> y;
        x--, y--;
        g[x].push_back ( y );
        g[y].push_back ( x );
    }

    for ( int i = 0; i < n; i++ )
        if ( ! vis[i] )
            dfs ( i );

    fout << comp << '\n';
    for ( int i = 0; i < comp; i++, fout << '\n' )
        for ( int x: c[i] )
            fout << 1 + x << ' ';


    return 0;
}