Cod sursa(job #3371931)

Utilizator nstefanNeagu Stefan nstefan Data 1 noiembrie 2026 20:25:36
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
#include <climits>
using namespace std;

using Graph = vector<vector<int>>;

vector<vector<int>> biconex(const Graph& g) {
  int in_time = 1;
  vector<int> in(g.size());
  vector<int> low(g.size(), INT_MAX);
  vector<vector<int>> ans;

  stack<int> s;

  auto dfs = [&](auto self, int node, int parent) -> void {
    s.push(node);
    low[node] = in[node] = in_time++;

    for (auto neigh : g[node]) {
      if (neigh == parent)
        continue;

      if (in[neigh] == 0) {
        self(self, neigh, node);
        low[node] = min(low[node], low[neigh]);

        // Detect the biconex component (this is similar to finding critical nodes)
        if (low[neigh] >= in[node]) {
          vector<int> comp;
          while (true) {
            int top = s.top();
            s.pop();
            comp.push_back(top);
            if (top == neigh)
              break;
          }
          comp.push_back(node); // push the node to component, but do NOT pop it
          ans.push_back(comp);
        }
      } else {
        low[node] = min(low[node], in[neigh]);
      }
    }
  };

  for (int i = 1; i < g.size(); i++)
    if (in[i] == 0)
      dfs(dfs, i, 0);

  return ans;
}

int main() {
  int n, m;
  cin >> n >> m;
  Graph g(n + 1);

  for (int i = 1; i <= m; i++) {
    int from, to; cin >> from >> to;
    g[from].push_back(to);
    g[to].push_back(from);
  }

  auto bc = biconex(g);
  cout << bc.size() << '\n';
  for (auto c : bc) {
    for (auto el : c)
      cout << el << ' ';
    cout << '\n';
  }
}