Cod sursa(job #3374721)

Utilizator MasterFire1990Balaban Nicolae Adrian MasterFire1990 Data 9 noiembrie 2026 09:42:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;
vector<int> a[100001], st;
vector<vector<int>> res;
int id[100001], low[100001], T;
void dfs(int u, int p) {
  id[u] = low[u] = ++T;
  st.push_back(u);
  for (int w : a[u]) {
    if (w == p)
      continue;
    if (id[w])
      low[u] = min(low[u], id[w]);
    else {
      dfs(w, u);
      low[u] = min(low[u], low[w]);
      if (low[w] >= id[u]) {
        vector<int> c;
        int x;
        do {
          x = st.back();
          st.pop_back();
          c.push_back(x);
        } while (x != w);
        c.push_back(u);
        res.push_back(c);
      }
    }
  }
}
int main() {
  ifstream f("biconex.in");
  ofstream g("biconex.out");
  int n, m;
  f >> n >> m;
  while (m--) {
    int x, y;
    f >> x >> y;
    a[x].push_back(y);
    a[y].push_back(x);
  }
  for (int i = 1; i <= n; i++)
    if (!id[i])
      dfs(i, 0);
  g << res.size() << "\n";
  for (auto &c : res) {
    for (int x : c)
      g << x << " ";
    g << "\n";
  }
}