Cod sursa(job #2869554)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 11 martie 2022 17:21:41
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

vector<int> gr[N], con[N];
stack<int> st;
int tin[N], nr_con, t;

int dfs(int nod) {
  st.push(nod);
  int ret = tin[nod] = ++t;
  for (auto vec: gr[nod]) {
    if (tin[vec] == 0) {
      int tvec = dfs(vec);
      if (tvec >= tin[nod]) {
        while (st.top() != nod) {
          con[nr_con].push_back(st.top());
          st.pop();
        }
        con[nr_con].push_back(nod);
        ++nr_con;
      }
      ret = min(ret, tvec);
    }
    ret = min(ret, tin[vec]);
  }
  return ret;
}

int main() {
  ifstream cin("biconex.in");
  ofstream cout("biconex.out");
  int n, m;
  cin >> n >> m;
  while (m--) {
    int x, y;
    cin >> x >> y;
    gr[x].push_back(y);
    gr[y].push_back(x);
  }
  cin.close();
  for (int i = 1; i <= n; ++i)
    if (tin[i] == 0)
      dfs(i);
  cout << nr_con << "\n";
  for (int i = 0; i < nr_con; ++i) {
    for (auto j: con[i])
      cout << j << " ";
    cout << "\n";
  }
  cout.close();
  return 0;
}