Cod sursa(job #3212619)

Utilizator AlexandruBenescuAlexandru Benescu AlexandruBenescu Data 11 martie 2024 23:20:51
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 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], ans[L];
int lev[L], t[L], s[L];
int r, st;

void dfs(int node){
  s[++st] = node;
  lev[node] = t[node];
  for (auto it : G[node])
    if (lev[it])
      lev[node] = min(lev[node], t[it]);
    else {
      int x = st;
      t[it] = /*lev[it] = */t[node] + 1;
      dfs(it);
      lev[node] = min(lev[it], lev[node]);
      if (lev[it] >= t[node]){
        ans[++r].push_back(node);
        while (st > x)
          ans[r].push_back(s[st--]);
      }
    }
}

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);
  }
  t[1] = lev[1] = 1;
  dfs(1);
  fout << r << "\n";
  for (int i = 1; i <= r; i++){
    for(auto it : ans[i])
      fout << it << " ";
    fout << "\n";
  }
  return 0;
}