Cod sursa(job #2876321)

Utilizator NanuGrancea Alexandru Nanu Data 23 martie 2022 10:45:11
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

#define DIM 100000

int n, m, nrcomp;
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) {
  pair<int, int> Nodes1 = {x, y}, Nodes2 = {y, x}, Nod;
  nrcomp++;
  do {
    Nod = St.top();
    Comp[nrcomp].push_back(Nod.first);    //scot toate muchiile din stiva pana ajung la muchia x, y sau y, x;
    Comp[nrcomp].push_back(Nod.second);
    St.pop();
  }while(Nod != Nodes1 && Nod != Nodes2);
}

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++) {
    sort(Comp[i].begin(), Comp[i].end());
    for(auto e : Comp[i])
      if(!fr[e]) {
        fout << e << " ";
        fr[e] = 1;
      }
    fout << '\n';

    for(auto e : Comp[i])
      fr[e] = 0;  //resetez nodurile afisate;
  }

  return 0;
}