#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <stack>
using namespace std;
//CLASA GRAPH DE BAZA
class Graph{
//DATELE MEMBRE
protected:
int m_number_of_nodes;
//numarul de noduri
//METODELE
public:
//functia de citire virtuala -> implementata diferit in fiecare dintre clase
virtual void read_graph(char *file);
//parcurgerea in latime
virtual vector<int> BFS(int node);
//parcurgerea in adancime
virtual void DFS(int node, vector<int>& visited);
};
//METODE PUBLICE
void Graph::read_graph(char *file) {
return;
}
vector<int> Graph::BFS(int node){
vector<int> aux;
return aux;
}
void Graph::DFS(int node, vector<int> &visited) {
return;
}
//CLASA UNORIENTED GRAPH
class Unoriented_graph:Graph{
protected:
vector< vector<int> > m_adjancency_list;
public:
//citirea grafului
void read_graph(char *file);
//parcurgerea in adancime DFS
void DFS(int node, vector<int>& visited);
//numararea componentelor conexe
int number_of_connected_components();
//returnarea unui vector cu componentele conexe
vector< unordered_set<int> > generate_biconnected_components();
private:
void DFSBiconnected(int current_node, int prec, int step, vector<int>& arrival_values, vector<int>& low_link_values,vector<unordered_set<int>>& biconnected_components,stack<pair <int, int>>& current_biconnected_components);
};
//METODE PUBLICE GRAFURI NEORIENTATE
void Unoriented_graph::read_graph(char *file) {
ifstream f(file);
vector<int> aux;
int number_edges;
//citim numarul de noduri si numarul de muchii
f>>this->m_number_of_nodes >> number_edges;
//rezervam in matricea de vecini spatiu pentru numarul de noduri ale grafului
this->m_adjancency_list.assign(this->m_number_of_nodes + 1, aux);
//citim fiecare muchie si o marcam pentru ambele capete
for(int i = 0; i < number_edges; i++){
int x,y;
f >> x >> y;
this->m_adjancency_list[x].push_back(y);
this->m_adjancency_list[y].push_back(x);
}
}
void Unoriented_graph::DFS(int node, vector<int> &visited) {
//marcam nodul curent ca vizitat
visited[node] = 1;
//parcurgem vecinii si pentru fiecare vecin nevizitat aplicam recursiv DFS
for(int i = 0; i < this->m_adjancency_list[node].size(); i++){
if(visited[ this->m_adjancency_list[node][i] ] == 0){
DFS( this->m_adjancency_list[node][i], visited);
}
}
}
int Unoriented_graph::number_of_connected_components() {
//numarul componentelor conexe il vom tine in nr
int number = 0;
//initial toate nodurile sunt nevizitate
vector<int> visited;
visited.assign(m_number_of_nodes + 1, 0);
//pentru fiecare nod nevizitat parcurgem din copil in copil prin DFS; de fiecare data cand dam de un nod nevizitat inseamna ca avem o noua componenta conexa
for(int node = 1; node <= this->m_number_of_nodes; node++){
if(visited[node] == 0){
number++;
DFS(node, visited);
}
}
return number;
}
vector< unordered_set<int> >Unoriented_graph::generate_biconnected_components(){
vector<unordered_set<int>> biconnected_components;
stack<pair <int, int>> current_biconnected_component;
vector<int> arrival_value;
vector<int> low_link_values;
//initializam timpii de sosire si nivelul cel mai de sus pentru fiecare nod
arrival_value.assign(this->m_number_of_nodes + 1, -1);
low_link_values.resize(this->m_number_of_nodes + 1);
//facem DFS
DFSBiconnected(1,0,0,arrival_value,low_link_values,biconnected_components,current_biconnected_component);
return biconnected_components;
}
//METODE PRIVATE GRAFURI NEORIENTATE
void Unoriented_graph::DFSBiconnected(int current_node, int prec, int step, vector<int>& arrival_values, vector<int>& low_link_values,vector<unordered_set<int>>& biconnected_components,stack<pair <int, int>>& current_biconnected_components){
//marcam ca vizitat nodul curent
arrival_values[current_node] = step;
//momentan nivelul minim de intoarcere e nivelul curent, adica pasul
low_link_values[current_node] = step;
//parcurgem vecinii nodului curent
for(int i = 0; i < this->m_adjancency_list[current_node].size(); i++){
int neighbor = this->m_adjancency_list[current_node][i];
if(neighbor != prec){
//verificam pe ce fel de muchie suntem
//daca vecinul curent a mai fost vizitat inseamna ca am dat de o muchie de intoarcere, altfel suntem pe o muchie in jos
if(arrival_values[neighbor] == -1){
//am dat de o noua muchie din componenta biconexa curenta, asa ca o adaugam in stiva
current_biconnected_components.push(make_pair(current_node, neighbor));
//apelam DFS pentru vecinul curent
DFSBiconnected(neighbor, current_node, step + 1,arrival_values,low_link_values,biconnected_components,current_biconnected_components);
//verificam daca atunci cand ne am dus mai departe in graf
// am dat de o muchie de intoarcere care ne duce mai sus decat ne ducea nodul acesta inainte
if(low_link_values[current_node] > low_link_values[neighbor]){
low_link_values[current_node] = low_link_values[neighbor];
}
//verificam daca am ajuns la finalul componentei biconexe
if(low_link_values[neighbor] >= arrival_values[current_node]){
//trebuie sa adaugam noua componenta biconexa in vectorul de componenete biconexe
//si sa golim stiva cu muchiile componentei biconexe curente
unordered_set<int> aux;
int aux1, aux2;
do{
aux1 = current_biconnected_components.top().first;
aux2 = current_biconnected_components.top().second;
aux.insert(aux1);
aux.insert(aux2);
current_biconnected_components.pop();
} while (aux1 != current_node || aux2 != neighbor);
biconnected_components.push_back(aux);
}
}else{
//avem o muchie de intoarcere, trebuie sa verificam daca nu cumva duce mai sus
if(low_link_values[current_node] > arrival_values[neighbor]){
low_link_values[current_node] = arrival_values[neighbor];
}
}
}
}
}
//CLASA ORIENTED GRAPH
class Oriented_graph:Graph{
protected:
vector< vector<int> > m_adjancency_list;
public:
void read_graph(char *file);
int read_graph_with_starting_node(char *file);
vector<int> BFS(int source);
};
//METODE PUBLICE ORIENTED GRAPHS
//citirea grafului orientat (fara costuri)
void Oriented_graph::read_graph(char *file) {
ifstream f(file);
vector<int> aux;
int number_edges;
//citim numarul de noduri si numarul de muchii
f >> m_number_of_nodes >> number_edges;
//rezervam in matricea de vecini spatiu pentru numarul de noduri ale grafului
this->m_adjancency_list.assign(this->m_number_of_nodes + 1, aux);
//citim fiecare muchie si o adaugam in lista de adiacenta, prin adagarea vecinului nodului din care porneste muchia
for(int i = 0; i < number_edges; i++){
int x,y;
f>>x>>y;
this->m_adjancency_list[x].push_back(y);
}
}
//citirea grafului orientat (fara costuri) cu nod de pornire
int Oriented_graph::read_graph_with_starting_node(char *file) {
ifstream f(file);
vector<int> aux;
int number_edges, source;
//citim numarul de noduri, numarul de muchii si nodul de pornire
f >> this->m_number_of_nodes >> number_edges >> source;
//reyervam spatiu in matricea de vecini pentru numarul de noduri ale grafului
this->m_adjancency_list.assign(this->m_number_of_nodes + 1, aux);
//parcurgem fiecare muchie si o adaugam in lista de adiacenta, prin adaugarea vecinului la nodul din care porneste muchia
for(int i=0; i<number_edges; i++){
int x,y;
f >> x >> y;
this->m_adjancency_list[x].push_back(y);
}
return source;
}
//BFS -> returneaza un vector in care pe pozitia i se afla numarul minim de arce ce trebuie parcurse de la sursa data pana la nodul i
vector<int> Oriented_graph::BFS(int source) {
//initializam vectorul de distante minime
vector<int> distances;
distances.assign(this->m_number_of_nodes + 1, 0);
int curent;
//in coada vom pune nodurile pe massura ce le parcurgem
queue<int> current_nodes;
//initial toate nodurile sunt nevizitate, asaa ca initializam visited[orice nod] = 0
vector<int> visited;
visited.assign(this->m_number_of_nodes + 1, 0);
//adaugam nodul sursa in coada si il marcam ca si vizitat
current_nodes.push(source);
visited[source] = 1;
//actualizam vectorul de distante pentru nodul curent cu distanta pana la el, adica 1
distances[source] = distances[source] + 1;
//facem BFS-ul
while( !current_nodes.empty() ){
curent = current_nodes.front();
//parcurgem vecinii nodului curent si pe fiecare vecin nevizitat il adaugam in coada, ii actualizam distanta pana la el si il marcam ca si vizitat
for(int i=0; i < this->m_adjancency_list[curent].size(); i++){
if(visited[ this->m_adjancency_list[curent][i] ] == 0){
current_nodes.push(this->m_adjancency_list[curent][i] );
distances[ current_nodes.back() ] = distances[curent] + 1;
visited[ this->m_adjancency_list[curent][i] ] = 1;
}
}
//am terminat cu nodul curent, il scoatem din coada
current_nodes.pop();
}
for(int i = 1; i <= this->m_number_of_nodes; i++){
distances[i]--;
}
return distances;
}
//CLASA UNORIENTED GRAPH WITH COSTS
class Unoriented_graph_with_costs:Unoriented_graph{
private:
};
//CLASA ORIENTED GRAPH WITH COSTS
class Oriented_graph_with_costs:Oriented_graph{
private:
};
//CLASA RETELE DE TRANSPORT
class Flow_network:Oriented_graph{
private:
};
//CLASA MULTIGRAF
class Multigraph:Graph{
private:
};
//HELPERE
void print_vector(vector<int> v, char *file){
ofstream g(file);
vector<int>::iterator it;
for(it = v.begin() + 1; it != v.end(); it++){
g << *it <<" ";
}
}
void print_vector_of_unordered_sets(vector< unordered_set<int> > v, char *file){
ofstream g(file);
vector< unordered_set<int> >::iterator it;
unordered_set<int>::iterator it_u;
g << v.size() << "\n";
for(it = v.begin(); it != v.end(); it++){
for(it_u = it->begin(); it_u != it->end(); it_u++){
g << *it_u << " ";
}
g << "\n";
}
}
int main() {
//BFS INFOARENA
/*Oriented_graph g;
int source;
vector<int> distances;
source = g.read_graph_with_starting_node("../bfs.in");
distances = g.BFS(source);
print_vector(distances, "../bfs.out");*/
//DFS INFOARENA
/*Unoriented_graph g;
ofstream out("../dfs.out");
int number;
g.read_graph("../dfs.in");
number = g.number_of_connected_components();
out << number;*/
//COMPONENTE BICONEXE INFOARENA
Unoriented_graph g;
vector< unordered_set<int> > biconnected_components;
g.read_graph("../biconex.in");
biconnected_components = g.generate_biconnected_components();
print_vector_of_unordered_sets(biconnected_components, "../biconex.out");
return 0;
}