Cod sursa(job #2539333)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 5 februarie 2020 20:04:54
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <vector>
#include <stack>

#define pb push_back

const int MAXN = 100000;

using namespace std;

ifstream cin( "biconex.in" );
ofstream cout( "biconex.out" );

int n, m, nrsol;

vector<int> g[MAXN+1];
vector<int> sol[MAXN+1];

bool viz[MAXN+1];

int nma[MAXN+1];
int lvl[MAXN+1];

stack<int> st;

int minim( int a, int b )
{
  if( b<a )
    a=b;

  return a;
}

void dfs( int source, int father )
{
  viz[source]=true;
  nma[source]=lvl[source]=lvl[father]+1;

  st.push(source);

  for( vector<int>::iterator it=g[source].begin();it!=g[source].end();it++ )
    if( *it!=father )
    {
      if( viz[*it] )
        nma[source]=minim(nma[source],lvl[*it]);
      else
      {
        dfs(*it,source);
        nma[source]=minim(nma[source],nma[*it]);

        //if( lvl[source]<=nma[*it] && source!=1 )
        //  cout<<source<<" este punct critic\n";

        //if( lvl[source]<nma[*it] )
        //  cout<<source<<" "<<*it<<" este muchie critica\n";

        if( nma[*it]>=lvl[source] )
        {
          nrsol++;

          while( !st.empty() && st.top()!=*it )
          {
            sol[nrsol].pb(st.top());
            st.pop();
          }

          sol[nrsol].pb(*it);
          st.pop();

          sol[nrsol].pb(source);
        }
      }
    }
}

int main()
{
  cin>>n>>m;

  for( int i=1;i<=m;i++ )
  {
    int x, y; cin>>x>>y;

    g[x].pb(y);
    g[y].pb(x);
  }

  dfs(1,0);

  cout<<nrsol;

  for( int i=1;i<=nrsol;i++ )
  {
    cout<<"\n";

    for( vector<int>::iterator it=sol[i].begin();it!=sol[i].end();it++ )
      cout<<*it<<" ";
  }

  return 0;
}