Pagini recente » Istoria paginii runda/simulare_nr1/clasament | Cod sursa (job #123054) | Istoria paginii utilizator/am.001 | Istoria paginii utilizator/liaioana | Cod sursa (job #2796129)
#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';
}
}