Cod sursa(job #2368420)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 5 martie 2019 16:02:32
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

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

const int NMAX = 100005;

int N, M;
vector <int> Ad[NMAX];

deque <int> S;

int disc[NMAX];
int low[NMAX];
int t;
int nr_comp;

vector <int> Comp[NMAX];

void Read()
{
fin >> N >> M;

int x, y;

for( int i = 1; i <= M; ++i )
{
fin >> x >> y;

Ad[x].push_back( y );
Ad[y].push_back( x );
}

fin.close();
}

void Dfs( int nod, int parent )
{
disc[nod] = low[nod] = ++t;

int w;

for( int i = 0; i < Ad[nod].size(); ++i )
{
w = Ad[nod][i];

if( w == parent ) continue;

if( disc[w] ) low[nod] = min( low[nod], disc[w] );
else
{
S.push_back( w );

Dfs( w, nod );

low[nod] = min( low[nod], low[w] );

if( low[w] >= disc[nod] )
{
++nr_comp;

S.push_back( nod );

while( !S.empty() && S.back() != w )
{
Comp[nr_comp].push_back( S.back() );
S.pop_back();
}

if( !S.empty() )
{
Comp[nr_comp].push_back( S.back() );
S.pop_back();
}
}
}
}
}

void Do()
{
Dfs( 1, 0 );

fout << nr_comp << '\n';

for( int i = 1; i <= nr_comp; ++i )
{
for( int j = 0; j < Comp[i].size(); ++j )
fout << Comp[i][j] << ' ';

fout << '\n';
}

}

int main()
{
Read();
Do();

return 0;
}