Cod sursa(job #3224212)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 14 aprilie 2024 22:10:28
Problema Componente biconexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
#define L 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n, m;
vector <int> G[L], bcc[L];
stack <int> st;
int lev[L], ru[L], bccCnt;

void add_bcc(int node, int targetSize) {
  while ((int)st.size() > targetSize) {
    bcc[bccCnt].push_back(st.top());
    st.pop();
  }
  bcc[bccCnt++].push_back(node);
}

void dfs(int node) {
  st.push(node);
  ru[node] = lev[node];
  for (auto it : G[node])
    if (lev[it])
      ru[node] = min(ru[node], ru[it]);
    else {
      int sz = st.size();
      lev[it] = lev[node] + 1;
      dfs(it);
      ru[node] = min(ru[node], ru[it]);
      if (ru[it] >= lev[node])
        add_bcc(node, sz);
    }
}

int main() {
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b;
    fin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  lev[1] = 1;
  dfs(1);

  fout << bccCnt << "\n";
  for (int i = 0; i < bccCnt; i++) {
    for (auto it : bcc[i])
      fout << it << " ";
    fout << "\n";
  }
  return 0;
}