Cod sursa(job #2739064)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 6 aprilie 2021 19:16:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 100000;

vector<int> graf[1 + NMAX];
int nivel[1 + NMAX];
int nivelMin[1 + NMAX];

vector<vector<int>> sol;

vector<int> stiva;

void adaugaComp(int nod)
{
  sol.emplace_back();

  while (stiva.back() != nod)
  {
    sol.back().emplace_back(stiva.back());
    stiva.pop_back();
  };

  sol.back().emplace_back(stiva.back());
  stiva.pop_back();
}

void dfs(int nod, int tata)
{
  stiva.emplace_back(nod);

  nivel[nod] = nivelMin[nod] = nivel[tata] + 1;

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

    if (fiu != tata)
    {
      if (nivel[fiu] == 0)
      {
        dfs(fiu, nod);

        nivelMin[nod] = min(nivelMin[nod], nivelMin[fiu]);

        if (nivelMin[fiu] >= nivel[nod])
        {
          adaugaComp(fiu);
          sol.back().emplace_back(nod);
        }
      }
      else
      {
        nivelMin[nod] = min(nivelMin[nod], nivel[fiu]);
      }
    }
  }
}

int main()
{
  ifstream in("biconex.in");
  ofstream out("biconex.out");

  int n, m;

  in >> n >> m;

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

    in >> x >> y;

    graf[x].emplace_back(y);
    graf[y].emplace_back(x);
  }

  dfs(1, 0);

  out << sol.size() << '\n';

  for (int i = 0; i < sol.size(); i++)
  {
    for (int j = 0; j < sol[i].size(); j++)
    {
      out << sol[i][j] << ' ';
    }

    out << '\n';
  }

  return 0;
}