Cod sursa(job #2725357)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 18 martie 2021 20:36:43
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int NMAX = 100000;

struct muchie {
  int dad, nod;
  muchie(int _dad = 0, int _nod = 0) : dad(_dad), nod(_nod) {}
};

int n, m;
int niv[NMAX + 5], highest[NMAX + 5];
vector<int> v[NMAX + 5];
vector<muchie> stiva;
vector<vector<int>> cbc;

void pop_cbc(int nod, int dad) {
  vector<int> new_cbc, aux;
  muchie crt;

  do {
    crt = stiva.back();
    stiva.pop_back();
    new_cbc.push_back(crt.dad);
    new_cbc.push_back(crt.nod);
  } while(crt.dad != dad || crt.nod != nod);

  sort(new_cbc.begin(), new_cbc.end());
  for(int i = 0; i < new_cbc.size(); i++)
    if(i == 0 || new_cbc[i] != new_cbc[i - 1])
      aux.push_back(new_cbc[i]);
  cbc.push_back(aux);
}

void dfs(int nod, int dad) {
  highest[nod] = niv[nod] = niv[dad] + 1;

  for(int vec: v[nod]) {
    if(vec == dad)
      continue;

    if(niv[vec] != 0)
      highest[nod] = min(highest[nod], niv[vec]);
    else {
      stiva.push_back(muchie(nod, vec));
      dfs(vec, nod);
      highest[nod] = min(highest[nod], highest[vec]);
      if(highest[vec] >= niv[nod])
        pop_cbc(vec, nod);
    }
  }
}

int main() {
  freopen("biconex.in", "r", stdin);
  freopen("biconex.out", "w", stdout);
  int x, y;

  scanf("%d %d", &n, &m);
  for(int i = 1; i <= m; i++) {
    scanf("%d %d", &x, &y);
    v[x].push_back(y);
    v[y].push_back(x);
  }

  dfs(1, 0);

  printf("%d\n", cbc.size());
  for(vector<int> crt_cbc: cbc) {
    for(int crt: crt_cbc)
      printf("%d ", crt);
    printf("\n");
  }

  return 0;
}