Cod sursa(job #2796129)

Utilizator DenisTroacaDenis Troaca DenisTroaca Data 7 noiembrie 2021 17:12:02
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.07 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

class Graph {
  int n; //nr de noduri
  int m; //nr de muchii
  vector < vector < int > > neighbors; //vector ce contine cate un vector cu vecini pt fiecare nod
  bool oriented; // variabiabila pt a verifca daca e orientat
  bool from1; // variabila pt a verifica daca nodurile sunt numerotate de la 1
  public:
    //constructori:
    Graph(int, bool, bool);
  Graph(int, int, bool, bool);

  void insert_edge(int, int); //functie pt a insera muchii

  vector < int > bfs(int); //functie pt a afla distantele minime de la un nod la celelate

  int connected_comp(); //functie pt a afla nr de componente conexe
  void dfs(int, vector < bool > & ); //functie pt parcurgerea in adancime a unei componente

  vector < vector < int > > biconnected_comp(); //functie pt a afla nr de componente biconexe
  void biconnected_dfs(int, int & , vector < int > & , vector < int > & , stack < int > & , vector < vector < int > > & ); //functie pt parcurgerea in adancime
};
Graph::Graph(int n, bool oriented = false, bool from1 = false) {
  this -> n = n;
  m = 0;
  this -> from1 = from1;
  this -> oriented = oriented;
  for (int i = 0; i < n; i++) {
    vector < int > aux;
    neighbors.push_back(aux);
  }
}
Graph::Graph(int n, int m, bool oriented = false, bool from1 = false) {
  this -> n = n;
  this -> m = m;
  this -> from1 = from1;
  this -> oriented = oriented;
  for (int i = 0; i < n; i++) {
    vector < int > aux;
    neighbors.push_back(aux);
  }
}

void Graph::insert_edge(int x, int y) {
  if (from1) {
    neighbors[x - 1].push_back(y - 1);
    if (!oriented)
      neighbors[y - 1].push_back(x - 1);
  } 
  else {
    neighbors[x].push_back(y);
    if (!oriented)
      neighbors[y].push_back(x);
  }
}

vector < int > Graph::bfs(int x) {
  vector < int > dist; //vector pt a memora distantele
  queue < int > aux; //coada ce retine nodurile ce trebuie explorate
  for (int i = 0; i < n; i++)
    //nodurile nevizitate primesc distanta -1:
    dist.push_back(-1);
  if (from1)
    x--;
  aux.push(x);
  dist[x] = 0;
  while (!aux.empty()) {
    for (int i = 0; i < neighbors[aux.front()].size(); i++) {
      //verificam daca nodurile vecine cu cel din varful cozii nu au fost vizitate:
      if (dist[neighbors[aux.front()][i]] == -1) {
        //retinem distanta:
        dist[neighbors[aux.front()][i]] = dist[aux.front()] + 1;
        //adaugam nodul vizitat in coada:
        aux.push(neighbors[aux.front()][i]);
      }
    }
    //trecem la urmatorul nod ce trebuie explorat:
    aux.pop();
  }
  return dist;
}

int Graph::connected_comp() {
  int nr = 0; //variabila pt a memora nr de componente conexe
  vector < bool > visited; // vector care verifica daca nodurile au fost vizitate
  for (int i = 0; i < n; i++)
    visited.push_back(false);
  for (int i = 0; i < n; i++) {
    if (visited[i] == false) {
      nr++;
      //facem parcurgere in adancime pt a vizita toate nodurile componentei conexe:
      dfs(i, visited);
    }
  }
  return nr;
}
void Graph::dfs(int x, vector < bool > & visited) {
  visited[x] = true;
  for (int i = 0; i < neighbors[x].size(); i++)
    if (visited[neighbors[x][i]] == false)
      dfs(neighbors[x][i], visited);
}

vector < vector < int > > Graph::biconnected_comp() {
  vector < int > disc; //vector cu timpurile de descoperie ale nodurilor din dfs
  vector < int > low; //vector cu timpurile de descoperie minime la care pot ajunge nodurile din dfs prin muchii de intoarcere
  stack < int > nodes; //stiva in care memoram nodurile vizitate
  vector < vector < int > > components; //vector cu componentele biconexe
  int disc_time = 0; //variabila pt a cunoaste timpul curent de descoperire

  for (int i = 0; i < n; i++) {
    disc.push_back(-1);
    low.push_back(-1);
  }
  for (int i = 0; i < n; i++) {
    if (disc[i] < 0) {
      biconnected_dfs(i, disc_time, disc, low, nodes, components);
      //dupa ce terminam dfs-ul, daca mai avem noduri in stiva, ele formeaza inca o componenta biconexa:
      if (!nodes.empty()) {
        vector < int > aux;
        while (!nodes.empty()) {
          aux.push_back(nodes.top());
          nodes.pop();
        }
        aux.push_back(i);
        components.push_back(aux);
      }
    }
  }
  return components;
}
void Graph::biconnected_dfs(int x, int & disc_time, vector < int > & disc, vector < int > & low, stack < int > & nodes, vector < vector < int > > & components) {
  disc[x] = disc_time;
  low[x] = disc_time;
  disc_time++;
  int children = 0; //variabila ce retine numar de copii al nodului
  for (int i = 0; i < neighbors[x].size(); i++) {
    if (disc[neighbors[x][i]] < 0) {
      children++;
      nodes.push(neighbors[x][i]);
      biconnected_dfs(neighbors[x][i], disc_time, disc, low, nodes, components);
      low[x] = min(low[x], low[neighbors[x][i]]);
      //daca nodul curent este radacina si are mai mult de un nod fiu
      //sau daca are un nod fiu care nu poate ajunge la un timp de descoperire mai mic decat al tatalui prin muchie de intoarcere
      //inseamna ca nodul curent este punct de articulatie
      if ((disc[x] == 0 && children > 1) || (disc[x] > 0 && disc[x] <= low[neighbors[x][i]])) {
        vector < int > aux; //variabila in care adaugam toate nodurile din componenta biconexa curenta(nodurile adaugate dupa punctul de articulatie)
        while (nodes.top() != neighbors[x][i]) {
          aux.push_back(nodes.top());
          nodes.pop();
        }
        nodes.pop();
        aux.push_back(neighbors[x][i]);
        aux.push_back(x);
        components.push_back(aux);
      }
    } 
    else //intre noduri e muchie de intoarcere
      low[x] = min(low[x], disc[neighbors[x][i]]);
  }
}

int main() {
  int n, m, a, b;
  fin >> n >> m;
  Graph g(n, m, false, true);
  for (int i = 0; i < m; i++) {
    fin >> a >> b;
    g.insert_edge(a, b);
  }
  vector < vector < int > > aux;
  aux = g.biconnected_comp();
  fout << aux.size() << '\n';
  for (int i = 0; i < aux.size(); i++) {
    for (int j = 0; j < aux[i].size(); j++)
      fout << aux[i][j] + 1 << " ";
    fout << '\n';
  }
}