Cod sursa(job #2795813)

Utilizator DenisTroacaDenis Troaca DenisTroaca Data 7 noiembrie 2021 00:19:30
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.22 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 > lvl;
  vector < int > min_lvl;
  stack < int > nodes;
  vector < vector < int > > components;

  for (int i = 0; i < n; i++) {
    lvl.push_back(-1);
    min_lvl.push_back(-1);
  }
  for (int i = 0; i < n; i++) {
    if (lvl[i] < 0) {
      biconnected_dfs(i, 0, lvl, min_lvl, nodes, components);
      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 current_lvl, vector < int > & lvl, vector < int > & min_lvl, stack < int > & nodes, vector < vector < int > > & components) {
  lvl[x] = current_lvl;
  min_lvl[x] = current_lvl;
  int children = 0;
  for (int i = 0; i < neighbors[x].size(); i++) {
    if (lvl[neighbors[x][i]] < 0) {
      children++;
      nodes.push(neighbors[x][i]);
      biconnected_dfs(neighbors[x][i], current_lvl + 1, lvl, min_lvl, nodes, components);
      min_lvl[x] = min(min_lvl[x], min_lvl[neighbors[x][i]]);
      if ((lvl[x] == 0 && children > 1) || (lvl[x] > 0 && lvl[x] <= min_lvl[neighbors[x][i]])) {
        vector < int > aux;
        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
      min_lvl[x] = min(min_lvl[x], lvl[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';
  }
}