Cod sursa(job #3220108)

Utilizator ezluciPirtac Eduard ezluci Data 2 aprilie 2024 13:59:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
using namespace std;
#ifdef EZ
   #include "./ez/ez.h"
   const string FILE_NAME = "test";
#else
   #include <bits/stdc++.h>
   const string FILE_NAME = "biconex";
#endif
#define mp make_pair
#define ll long long
#define pb push_back
#define fi first
#define se second
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

const int nMAX = 1e5;

int n, m;
vector<int> gf[nMAX + 1];


int niv[nMAX + 1];
int up[nMAX + 1];
bool viz[nMAX + 1];
vector<pair<int, int>> stiv;
vector<vector<int>> comps;

void dfs(int nod, int dad)
{
   niv[nod] = niv[dad] + 1;
   up[nod] = niv[nod];
   viz[nod] = 1;

   for (int nex : gf[nod])
   {
      if (viz[nex])
      {
         if (nex != dad)
            up[nod] = min(up[nod], niv[nex]);
         continue;
      }

      stiv.pb(mp(nod, nex));

      dfs(nex, nod);
      up[nod] = min(up[nod], up[nex]);

      if ( !(up[nex] < niv[nod]) )
      {
         comps.pb({});
         while (stiv.back() != mp(nod, nex))
            comps.back().pb(stiv.back().se),
            stiv.pop_back();
         comps.back().pb(nex);
         comps.back().pb(nod);
         stiv.pop_back();
      }
   }
}


int main()
{
   cin >> n >> m;
   for (int i = 1; i <= m; ++i)
   {
      int a, b;   cin >> a >> b;
      gf[a].pb(b);   gf[b].pb(a);
   }

   dfs(1, 0);

   cout << comps.size() << '\n';
   for (const auto &comp : comps)
   {
      for (int x : comp)  cout << x << ' ';
      cout << '\n';
   }
}