Cod sursa(job #2418294)

Utilizator capmareAlexCapmare Alex capmareAlex Data 4 mai 2019 15:51:52
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define MMAX 200005

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
vector < int > v[NMAX], sol[NMAX];
deque< int > q;
int level[NMAX], used[NMAX], low[NMAX];
int bicon;
void dfs( int k, int dad)
{
    level[k] = level[dad] + 1;
    low[k] = level[k];
    used[k] = 1;
    q.push_back(k);
    for( auto x : v[k])
      {
          if(x == dad)continue;
          if(used[x])
          {
              low[k] = low[k] < level[x] ? low[k] : level[x];

          }
          else
          {
              dfs(x, k);
              low[k] = low[x] < low[k]? low[x] : low[k];
              if( low[x] >= level[k])
              {
                  ++bicon;
                  int t;
                  do
                  {
                      t=q.back();
                      q.pop_back();
                      sol[bicon].push_back(t);
                  }
                  while(q.size()&&t!=x);
                  sol[bicon].push_back(k);
              }

          }
      }
}
int main()
{
    fin >>n >>m;
    while ( m )
    {
        int x, y;
        fin >>x >>y;
        v[x].push_back(y);
        v[y].push_back(x);
        --m;
    }
    dfs(1,0);
    fout << bicon <<"\n";
    for( int i = 1; i <= bicon; ++i, fout << "\n")
        for( int j = 0; j <sol[i].size(); ++j, fout<< " ")fout<<sol[i][j];
    return 0;
}