Cod sursa(job #2719486)

Utilizator Iulia25Hosu Iulia Iulia25 Data 9 martie 2021 21:44:13
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 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], viz2[N];
pair <int, int> stiva[N];
bool art[N];
vector <int> v[N];
vector <int> 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]);
  }
}

bool cmp(int x, int y)  {
  return l[x] > l[y];
}

void dfs2(int nod, int last) {
  viz2[nod] = -1;
  stiva[++top] = {last, nod};
  sort (v[nod].begin(), v[nod].end(), cmp);
  for (auto it : v[nod])  {
    if (viz2[it] != -1) {
      dfs2(it, nod);
      if (l[it] >= viz[nod]) {
        ++nrc;
        while (stiva[top].second != nod)
          ans[nrc].push_back(stiva[top--].second);
        ans[nrc].push_back(nod);
        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;
}