Cod sursa(job #2371273)

Utilizator liviu2000Dragomirescu Liviu liviu2000 Data 6 martie 2019 17:00:31
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
#define N 100005

using namespace std;

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

vector<int> graf[N] , sol[N] ;
int n , m ,ct;
bool viz[N] ;
int nivel[N] , low[N] ;
stack<int> st;

void citire()
{
    int i , x , y ;
    fin >> n >> m ;
    for ( i = 1; i <= m ; i++)
    {
        fin >> x >> y ;
        graf[x].push_back(y) ;
        graf[y].push_back(x) ;
    }
}

void adaug(int nod,int vv)
{
    ct++ ;
    sol[ct].push_back(nod) ;
    do
    {
        sol[ct].push_back(st.top()) ;
        st.pop() ;
    } while ( sol[ct][sol[ct].size()-1] != vv ) ;
}

void dfs(int nod,int tt)
{
    viz[nod] = true ;
    nivel[nod] = nivel[tt]+1 ;
    low[nod] = nivel[nod] ;
    st.push(nod) ;
    for ( auto vec : graf[nod] )
    {
        if ( vec == tt )
            continue ;
        if ( viz[vec] == false )
        {
            dfs(vec,nod) ;
            low[nod] = min(low[nod],low[vec]) ;
            if ( low[vec] >= nivel[nod] )
                adaug(nod,vec) ;
        }
        else
            low[nod] = min(low[nod],nivel[vec]) ;
    }
}

int main()
{
    citire() ;
    for ( int i = 1 ; i <= n ; i++ )
        if ( viz[i] == false )
            dfs(i,0) ;
    fout << ct << '\n';
    for ( int i = 1 ; i <= ct ; i++ )
    {
        for ( auto xx : sol[i] )
            fout << xx << " " ;
        fout << '\n' ;
    }
}