Cod sursa(job #3005278)

Utilizator dorufDoru Floare doruf Data 16 martie 2023 20:56:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;

const string task("biconex");

ifstream fin(task + ".in");
ofstream fout(task + ".out");

const int N = 100000 + 5;
int n, m, vis[N], lma[N], lvl[N];
vector<int> adj[N];
stack<int> st;
vector<vector<int>> cbic;

void dfs(int u, int p) {
  vis[u] = 1;
  lvl[u] = lma[u] = lvl[p] + 1;
  st.push(u);
  for (auto v : adj[u]) {
    if (v == p) continue;
    if (vis[v])
      lma[u] = min(lma[u], lvl[v]);
    else {
      dfs(v, u);
      lma[u] = min(lma[u], lma[v]);
      if (lma[v] >= lvl[u]) {
        vector<int> comp;
        while (st.top() != v) {
          comp.push_back(st.top());
          st.pop();
        }
        comp.push_back(u);
        comp.push_back(v);
        cbic.push_back(comp);
        st.pop();
      }
    }
  }
}

int main() {
  fin >> n >> m;
  while (m--) {
    int u, v; fin >> u >> v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  for (int i = 1; i <= n; ++i)
    if (!vis[i])
      dfs(i, 0);
  fout << cbic.size() << '\n';
  for (auto i : cbic) {
    for (auto j : i)
      fout << j << ' ';
    fout << '\n';
  }
}