Cod sursa(job #2802631)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 18 noiembrie 2021 16:06:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int N = 1e5 + 5;

stack<int> st;
vector<int> gr[N], ans[N];
int niv[N], nr_con;

int dfs(int nod) {
  int niv_min = niv[nod];
  for (auto vec : gr[nod]) {
    if (niv[vec] == 0) {
      int sz = st.size();
      niv[vec] = 1 + niv[nod];
      int niv_min_crt = dfs(vec);
      if (niv_min_crt >= niv[nod]) {
        while (st.size() > sz) {
          ans[nr_con].push_back(st.top());
          st.pop();
        }
        ans[nr_con].push_back(nod);
        ++nr_con;
      }
      niv_min = min(niv_min_crt, niv_min);
    }
    niv_min = min(niv_min, niv[vec]);
  }
  st.push(nod);
  return niv_min;
}

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 (niv[i] == 0) {
      niv[i] = 1;
      dfs(i);
    }
  cout << nr_con << "\n";
  for (int i = 0; i < nr_con; ++i) {
    for (auto j : ans[i])
      cout << j << " ";
    cout << "\n";
  }
  cout.close();
  return 0;
}