Cod sursa(job #2719455)

Utilizator Iulia25Hosu Iulia Iulia25 Data 9 martie 2021 21:11:55
Problema Componente biconexe Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int N = 1e5 + 5;

int timp = 1, n, m, top, nrc;
int l[N], viz[N], stiva[N];
bool art[N];
vector <int> v[N], ans[N];

void dfs(int nod, int last) {
  viz[nod] = l[nod] = timp;
  int fii = 0;
  for (auto it : v[nod])  {
    if (!viz[it]) {
      ++timp;
      dfs(it, nod);
      ++fii;
      if (nod != 1 && l[it] >= viz[nod] || nod == 1 && fii > 1) {
        art[nod] = true;
      }
    }
    if (it != last)
      l[nod] = min(l[nod], l[it]);
  }
}

void dfs2(int nod, int last) {
  viz[nod] = -1;
  stiva[++top] = nod;
  for (auto it : v[nod])  {
    if (viz[it] != -1) {
      dfs2(it, nod);
      if (art[nod]) {
        ++nrc;
        ans[nrc].push_back(nod);
        while (stiva[top] != nod)
          ans[nrc].push_back(stiva[top--]);
        sort (ans[nrc].begin(), ans[nrc].end());
      }
    }
  }
}

int main()  {
  cin >> n >> m;
  int x, y;
  for (int i = 1; i <= m; ++i)  {
    cin >> x >> y;
    v[x].push_back(y);
    v[y].push_back(x);
  }
  dfs(1, 0);
  dfs2(1, 0);
  cout << nrc << '\n';
  for (int i = 1; i <= nrc; ++i)  {
    for (auto it : ans[i])
      cout << it << ' ';
    cout << '\n';
  }
  return 0;
}