Cod sursa(job #2876270)

Utilizator NanuGrancea Alexandru Nanu Data 23 martie 2022 10:30:12
Problema Componente biconexe Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

#define DIM 100000

int n, m, nrcomp, radacina, nr;
bool sel[DIM + 1], fr[DIM + 1];
int low[DIM + 1], nvl[DIM + 1], t[DIM + 1];
vector <int> G[DIM + 1];
vector <int> Comp[DIM + 1]; //retin fiecare componenta biconexa;
stack <pair<int, int>> St;

static inline void Save_comp(int x, int y) {
  int st, dr;
  nrcomp++;
  do {
    st = St.top().first;
    dr = St.top().second;
    Comp[nrcomp].push_back(st);
    Comp[nrcomp].push_back(dr);
    St.pop();
  }while(x != st && y != dr && x != dr && y != st);
}

static inline void dfs(int nod) {
  sel[nod] = 1;
  low[nod] = nvl[nod];

  for(auto e : G[nod]) {
    if(e != t[nod] && nvl[e] < nvl[nod])
      St.push({nod, e});

    if(!sel[e]) {
      nvl[e] = nvl[nod] + 1;
      t[e] = nod;

      dfs(e);

      if(low[e] < low[nod])
        low[nod] = low[e];

      if(low[e] >= nvl[nod])
        Save_comp(nod, e);
    }else if(e != t[nod] && nvl[e] < low[nod])
      low[nod] = nvl[e];
  }
}

int main() {
  fin.tie();
  fout.tie();
  
  fin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int x, y;

    fin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }

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

  fout << nrcomp << '\n';
  for(int i = 1; i <= nrcomp; i++) {
    for(auto e : Comp[i])
      if(!fr[e]) {
        fout << e << " ";
        fr[e] = 1;
      }
    fout << '\n';

    for(int i = 1; i <= n; i++)
      fr[i] = 0;

  }

  return 0;
}