Cod sursa(job #2814757)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 8 decembrie 2021 16:04:33
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int N = 1e5 + 5;

vector<int> gr[N], bi[N];
int t[N], tmin[N], con;
stack<int> st;


void add_bicon(int nod, int fiu) {
  while (!st.empty() && st.top() != fiu) {
    bi[con].push_back(st.top());
    st.pop();
  }
  bi[con].push_back(fiu);
  bi[con].push_back(nod);
  st.pop();
  ++con;
}

void dfs(int nod, int tata) {
  st.push(nod);
  for (auto vec: gr[nod]) {
    if (t[vec] == 0) {
      t[vec] = tmin[vec] = t[nod] + 1;
      dfs(vec, nod);
      tmin[nod] = min(tmin[nod], tmin[vec]);
      if (tmin[vec] >= t[nod])
        add_bicon(nod, vec);
    }
    if (vec != tata)
      tmin[nod] = min(tmin[nod], t[vec]);
  }
}

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