Cod sursa(job #2368386)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 5 martie 2019 15:51:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 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;
}