Cod sursa(job #2576275)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 6 martie 2020 18:14:48
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100005;

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

int disc[NMAX];
int low[NMAX];
vector <int> S;
vector < vector <int> > _ans;
int t;

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

    int a, b;
    for( int i = 1; i <= M; ++i ) {
       fin >> a >> b;

       Ad[a].push_back( b );
       Ad[b].push_back( a );
    }
}

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

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

       if( w == parent ) continue;

       if( disc[w] > 0 ) low[nod] = min( low[nod], disc[w] );
       else {
          Dfs( w, nod );
          low[nod] = min( low[nod], low[w] );

          if( low[w] >= disc[nod] ) {
             vector <int> tmp;

             while( S.back() != w ) {
                tmp.push_back( S.back() );
                S.pop_back();
             }
             tmp.push_back( S.back() );
             S.pop_back();

             tmp.push_back( nod );
             _ans.push_back( tmp );
          }
       }
    }

}

void Do() {
    for( int i = 1; i <= N; ++i )
      if( disc[i] == 0 ) Dfs( i, 0 );

    fout << _ans.size() << '\n';
    for( int i = 0; i < _ans.size(); ++i ) {
       for( int j = 0; j < _ans[i].size(); ++j )
         fout << _ans[i][j] << ' '; fout << '\n';
    }
}

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

    fin.close();
    fout.close();

    return 0;
}