Cod sursa(job #2130343)

Utilizator stefan_creastaStefan Creasta stefan_creasta Data 13 februarie 2018 17:08:45
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 100005;
vector <int> v[NMAX];
vector <int> sol[NMAX];
int s = 0, top = 0;
int st[NMAX];
int a[NMAX], b[NMAX];
void dfs(int nod) {
  st[++top] = nod;
  for(auto it : v[nod]) {
    if(a[it] == 0) {
      int lim = top;
      b[it] = a[nod] + 1;
      a[it] = a[nod] + 1;
      dfs(it);
      b[nod] = min(b[nod], b[it]);
      if(a[nod] <= b[it]) {
        sol[++s].push_back(nod);
        while(top > lim) {
          sol[s].push_back(st[top--]);
        }
      }
    }
    else {
      b[nod] = min(a[it], b[nod]);
    }
  }
}

int main() {
  int n, m;
  freopen("biconex.in", "r", stdin);
  freopen("biconex.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    v[x].push_back(y);
    v[y].push_back(x);
  }
  dfs(1);
  printf("%d\n", s);
  for(int i = 1; i <= s; ++i) {
    for(auto it : sol[i]) {
      printf("%d ", it);
    }
    printf("\n");
  }
  return 0;
}