#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <stack>
#include <algorithm>
#include <set>
using namespace std;
vector<int> default_vector;
//CLASA DE BAZA GRAPH
class Graph{
protected:
//numarul de noduri ale grafului
int m_number_of_nodes;
//listele de adiacenta
vector< vector<int> > m_adjacency_list;
//metoda hakimi -> intoarce true daca se poate construi un graf din secventa data ca argument si false in caz contrar
bool hakimi(vector<int> v);
public:
//CONSTRUCTORII
//constructorul cu 2 parametri: numarul de noduri si matricea de vecini
Graph(int number_of_nodes, const vector< vector<int> > &adjacency_list);
//constructorul care primeste doar numarul de noduri
Graph(int number_of_nodes);
//constructorul care primeste doar lista de adiacenta
Graph(const vector< vector<int> > &adjacency_list);
//PARCURGERILE
//BFS(int nod) -> imi returneaza un vector in care pe fiecare pozitie i avem numarul minim de muchii ce trebuie parcurse pentru
//a ajunge de la nodul sursa dat la nodul i
virtual vector<int> BFS(int source);
//DFS(int node, vector<int>& visited) -> parcurge prin DFS graful pornind din nodul sursa dat ca argument si folosind vectorul de noduri
//vizitate, care in cazul in care nu se da va fi considerat pe toate pozitiile 0(toate nodurile sunt nevizitate)
virtual void DFS(int source, vector<int>& visited = default_vector);
};
//METODE PUBLICE ALE CLASEI DE BAZA GRAPH
//CONSTRUCTORII
//constructorul care primeste 2 parametri: numarul de noduri si matricea de vecini
Graph::Graph(int number_of_nodes, const vector< vector<int> > &adjacency_list) : m_adjacency_list(adjacency_list) {
//dupa ce am setat matricea de vecini ca fiind matricea data, setam ca numarul de noduri ale grafului sa fie cel dat
m_number_of_nodes = number_of_nodes;
}
//constructorul cu un singur parametru: numarul de noduri
Graph::Graph(int number_of_nodes){
//setam numarul de noduri ale grafului
m_number_of_nodes = number_of_nodes;
//rezervam spatiu in matricea de vecini: cate un vector de vecini pentru fiecare nod al grafului, incepand de la 1 asa ca mai adaugam 1
m_adjacency_list.assign(m_number_of_nodes + 1, vector<int>());
}
//constructorul care primeste un singur parametru: matricea de vecini
Graph::Graph(const vector< vector<int> > &adjacency_list) : m_adjacency_list(adjacency_list) {
//dupa ce am setat matricea de vecini, setam numarul de noduri ca fiind egal cu numarul de linii ai matricei de vecini
m_number_of_nodes = m_adjacency_list.size();
}
//PARCURGERILE
//BFS: O(numar noduri + numar muchii)
vector<int> Graph::BFS(int source) {
//initializam vectorul de distante minime de la nodul sursa la fiecare nod; initial toate distantele sunt 0
vector<int> distances;
distances.assign(this->m_number_of_nodes + 1, 0);
int curent;
//folosim o coada in care vom pune nodurile pe masura ce le parcurgem
queue<int> current_nodes;
//initial toate nodurile sunt nevizitate, asa 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 distances pentru nodul curent cu distanta pana la el, adica 1
distances[source] = distances[source] + 1;
//facem BFS-ul; cat timp mai avem noduri de parcurs in coada, luam cate un nod din coada si ii parcurgem vecinii;
//pentru fiecare vecini nevizitat, actualizam distanta pana la el, il marcam ca si vizitat si il adaugam in coada cu noduri de vizitat, urmand sa facem
//aceiasi pasi si pentru el, dar abia atunci cand va veni randul lui in coada
while( !current_nodes.empty() ){
curent = current_nodes.front();
//parcurgem vecinii nodului curent si verificam pentru fiecare daca este vizitat
for(int i=0; i < this->m_adjacency_list[curent].size(); i++){
if(visited[ this->m_adjacency_list[curent][i] ] == 0){
//nodurile nevizitate se adauga la finalul cozii de parcurs
current_nodes.push(this->m_adjacency_list[curent][i] );
//actualizam distanta catre vecinul nodului curent; noua distanta este distanta cu care am ajuns pana la nodul curent + 1
distances[ current_nodes.back() ] = distances[curent] + 1;
//marcam vecinul ca vizitat
visited[ this->m_adjacency_list[curent][i] ] = 1;
}
}
//am terminat cu nodul curent, il scoatem din coada
current_nodes.pop();
}
//scadem cu 1 fiecare distanta din vectorul de distante
for(int i = 1; i <= this->m_number_of_nodes; i++){
distances[i]--;
}
return distances;
}
//DFS: O(numar noduri + numar muchii)
void Graph::DFS(int source, vector<int> &visited) {
//daca nu am primit un vector de noduri vizitate, il creem noi, considerand toate nodurile nevizitate
if(visited.size() == 0){
visited.assign(m_number_of_nodes + 1, 0);
}
//marcam nodul curent ca vizitat
visited[source] = 1;
//parcurgem vecinii si pentru fiecare vecin nevizitat aplicam recursiv DFS
for(int i = 0; i < this->m_adjacency_list[source].size(); i++){
if(visited[ this->m_adjacency_list[source][i] ] == 0){
DFS( this->m_adjacency_list[source][i], visited);
}
}
}
//Havel Hakimi: O(n^2 log n)
bool Graph::hakimi(vector<int> v){
//daca suma gradelor nodurilor nu este para, automat nu se va putea face un graf din secventa, asa ca verificam acest lucru mai intai
//daca vreuna din valorile din secventa este mai mare sau egala cu numarul de noduri, automat nu va putea fi epuizat gradul acelui nod si, implicit,
//nu se va putea construi graf din secventa v, asa ca verificam si acest lucru
int sum =0;
for(int i = 0; i < v.size(); i++){
if(v[i] >= v.size()) return false;
sum = sum + v[i];
}
if(sum % 2 == 1) return false;
//sortam descrescator gradele din secventa
sort(v.begin(), v.end(), greater<int>());
//incercam sa epuizam gradele
while(v[0] != 0){
//parcurgem toate nodurile si le legam(scazand gradul fiecaruia)
for(int i = 0; i <= v[0]; i++){
v[i]--;
//daca se ajunge la valori negative pentru grad inseamna ca graful nu poate fi format
if(v[i] < 0) return false;
}
v[0] = 0;
sort(v.begin(), v.end(), greater<int>());
}
return true;
}
//CLASA GRAF NEORIENTAT FARA COSTURI
class Undirected_graph: protected Graph{
public:
//CONSTRUCTORI
//constructorul care ia 2 parametri: numarul de noduri si matricea de vecini
Undirected_graph(int number_of_nodes, const vector< vector<int> > &adjancency_list);
//constructorul care ia 1 parametru: numarul de noduri
Undirected_graph(int number_of_nodes);
//constructorul care ia 2 parametri: matricea de vecini
Undirected_graph(const vector< vector<int> > &adjacency_list);
//ALGORITMI
//numararea componentelor conexe
int number_of_connected_components();
//returnarea unui vector cu componentele conexe
vector< unordered_set<int> > generate_biconnected_components();
//gasirea muchiilor critice
vector< vector<int> > find_critical_edges();
private:
//DFS-ul folosit la gasirea componentelor biconexe
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);
//DFS-ul folosit la gasirea muchiilor critice
void DFSCriticals(int current_node, int& step, vector<int>& visited, vector<int>& prec, vector<int>& low_link_values, vector<int>& arrival_times, vector< vector<int> >& critical_edges);
};
//METODE PUBLICE ALE CLASEI GRAF NEORIENTAT FARA COSTURI
//CONTRUCTORI
//constructorul cu 2 parametri: numarul de noduri si matricea de vecini
Undirected_graph::Undirected_graph(int number_of_nodes, const vector<vector<int>> &adjancency_list) : Graph(number_of_nodes, adjancency_list) {}
//constructorul cu 1 parametru: numarul de noduri
Undirected_graph::Undirected_graph(int number_of_nodes) : Graph(number_of_nodes) {}
//constructorul cu 1 parametru: matricea de adiacenta
Undirected_graph::Undirected_graph(const vector< vector<int> > &adjacency_list) : Graph(adjacency_list) {}
//ALGORITMI
//NUMARUL DE COMPONENTE CONEXE INTR-UN GRAF NEORIENTAT: O(numar noduri + numar muchii)
int Undirected_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 node 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;
}
//NUMARUL DE COMPONENTE BICONEXE DIN GRAFUL NEORIENTAT: O(numar de noduri + numar de muchii)
vector< unordered_set<int> >Undirected_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 cu 0 pentru fiecare nod si rezervam spatiu pentru vectorul cu nivelul cel mai de sus accesibil pentru fiecare nod al grafului
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);
//returnam vectorul de componente biconexe modificat in urma DFS-ului
return biconnected_components;
}
//GASIREA MUCHIILOR CRITICE: O(numar noduri + numar muchii)
vector< vector<int> > Undirected_graph::find_critical_edges() {
int current_arrival_time = 0;
vector< vector<int> > critical_edges;
vector<int> visited;
vector<int> prec;
vector<int> low_link_values;
vector<int> arrival_times;
//initializam toate nodurile ca fiind nevizitate
visited.assign(m_number_of_nodes + 1, 0);
//rezervam spatiu pentru vectorul de precedenti ai fiecarui nod din graf
prec.resize(m_number_of_nodes + 1);
//rezervam loc pentru vectorul in care pentru fiecare nod din graf retinem cel mai de sus nivel la care poate ajunge acel nod
low_link_values.resize(m_number_of_nodes + 1);
//initializam timpii de ajungere la fiecare nod din graf
arrival_times.assign(m_number_of_nodes + 1, -1);
//parcurgem nodurile grafului si, pentru fiecare nod nevizitat, facem DFS
for(int i = 1; i <= m_number_of_nodes; i++){
if(visited[i] == 0){
DFSCriticals(i, current_arrival_time, visited, prec, low_link_values, arrival_times, critical_edges);
}
}
return critical_edges;
}
//METODE PRIVATE GRAFURI NEORIENTATE
//DFS-ul pe care il folosim la detereminarea componentelor biconexe
void Undirected_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_adjacency_list[current_node].size(); i++){
int neighbor = this->m_adjacency_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;
//ne formam in aux componenta biconexa si apoi o adaugam in vectorul de componente biconexe
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, caz in care sa actualizam nivelul minim la care se poate ajunge din nodul curent
if(low_link_values[current_node] > arrival_values[neighbor]){
low_link_values[current_node] = arrival_values[neighbor];
}
}
}
}
}
//DFS-ul pe care il folosim in gasirea muchiilor critice
void Undirected_graph::DFSCriticals(int current_node, int &step, vector<int> &visited, vector<int> &prec,
vector<int> &low_link_values, vector<int> &arrival_times,
vector<vector<int>> &critical_edges) {
//marcam nodul ca vizitat in vectorul visited, actualizam timpul lui de ajungere iar low link value momentan e fix timpul de ajungere
visited[current_node] = 1;
arrival_times[current_node] = step;
low_link_values[current_node] = step;
//crestem timpul de ajungere pentru urmatorul DFS
step++;
//parcurgem vecinii nodului
for(int i = 0; i < m_adjacency_list[current_node].size(); i++){
int neighbor = m_adjacency_list[current_node][i];
//pentru fiecare vecin nevizitat, ii actualizam precedentul ca fiind nodul ai carui vecini ii parcurgem si intram in parcurgerea vecinilor vecinului
if (visited[neighbor] == 0){
prec[neighbor] = current_node;
DFSCriticals(neighbor, step, visited, prec, low_link_values, arrival_times, critical_edges);
//la iesirea din DFS incercam sa minimizam low link value pentru nodul curent, in cazul in care vecinul poate ajunge la un node mai indepartat
if(low_link_values[current_node] > low_link_values[neighbor]){
low_link_values[current_node] = low_link_values[neighbor];
}
//in cazul in care este o muchie critica, o adaugam in vectorul de muchii critice
if (low_link_values[neighbor] > arrival_times[current_node]){
critical_edges.push_back({current_node, neighbor});
}
}
else{
//pentru fiecare vecin deja vizitat incercam sa minimzam low link value pentru nodul nostru
if (neighbor != prec[current_node]){
if(low_link_values[current_node] > arrival_times[neighbor]){
low_link_values[current_node] = arrival_times[neighbor];
}
}
}
}
}
//CLASA GRAF NEORIENTAT BIPARTIT
class Unoriented_bipartite_graph: Undirected_graph{
private:
int m_number_of_left_nodes;
public:
//CONSTRUCTORI
//constructor cu 3 parametri: numarul de noduri, matricea de vecini si numarul de noduri din multimea din stanga
Unoriented_bipartite_graph(int number_of_nodes, const vector<vector<int>> &adjacency_list, int number_of_left_nodes);
//constructorul cu 3 parametri: numarul de noduri din stanga, numarul de noduri din dreata si lista de adiacenta
Unoriented_bipartite_graph(int number_of_left_nodes, int number_of_right_nodes, const vector< vector<int> > &adjacency_list);
//returnarea cuplajului maxim
vector< pair<int, int> > hopcroft_karp();
private:
//DFS-ul folosit in gasirea cuplajului maixm in hopcroft_karp()
bool DFS(int node, vector<int>& left_pair, vector<int>& right_pair, vector<int>& visited);
};
//METODE PUBLICE ALE CLASEI DE GRAF NEORIENTAT BIPARTIT
//CONSTRUCTORI
//constructorul cu 3 parametri: numarul de noduri, matricea de vecini si numarul de noduri din stanga
Unoriented_bipartite_graph::Unoriented_bipartite_graph(int number_of_nodes, const vector< vector<int> > &adjacency_list,
int number_of_left_nodes) : Undirected_graph(adjacency_list){
//dupa ce am apelat constructorul clasei de baza pentru matricea de vecini(care contine doar nodurile din multimea din stanga),
//setam numarul de noduri din stanga cu cel dat si numarul total de noduri
m_number_of_left_nodes = number_of_left_nodes;
m_number_of_nodes = number_of_nodes;
}
//constructorul cu 3 parametri: numarul de noduri din stanga, numarul de noduri din dreapta si matricea de vecini
Unoriented_bipartite_graph::Unoriented_bipartite_graph(int number_of_left_nodes, int number_of_right_nodes,
const vector< vector<int> > &adjacency_list) : Undirected_graph(adjacency_list){
//dupa ce am setat matricea de adiacenta cu cea data, setam numarul de noduri din stanga cu numarul dat si numarul total de noduri va fi suma celor din stanga cu cele din dreapta
m_number_of_left_nodes = number_of_left_nodes;
m_number_of_nodes = number_of_left_nodes + number_of_right_nodes;
}
//ALGORITMI
//metoda hopcroft_karp() returneaza cuplajul maxim
vector<pair<int, int>> Unoriented_bipartite_graph::hopcroft_karp() {
vector< pair<int,int> > maximum_matching;
vector<int> right_pair;
vector<int> left_pair;
vector<int> distances;
vector<int> visited;
//initializam vectorul de perechi din dreapta pentru numarul de noduri din stanga; cand valoarea e -1, inseamna ca acel nod nu are pereche in dreapta
right_pair.assign(m_number_of_left_nodes + 1, -1);
//initializam vectorul de perechi din stanga pentru numarul de noduri din dreapta; cand valoarea e -1, inseamna ca acel nod nu are pereche in stanga
left_pair.assign(m_number_of_nodes - m_number_of_left_nodes + 2, -1);
//initializam vectorul de distante pentru numarul de noduri din stanga
distances.assign(m_number_of_left_nodes + 1, 0);
//vom tot actualiza cuplajul maxim atata timp cat avem un lant inca negasit
//vom retine intr-o variabila daca mai avem lanturi proaspat gasite sau nu; ne vom opri cand nu mai gasim niciun lant
int enough = 0;
while(enough == 0){
//pornim cu ideea ca nu vom mai gasi lant
enough = 1;
//reinitiliazam toate nodurile ca neviyitate, intrucat incepem cu un nou lant
visited.assign(m_number_of_nodes + 1, 0);
//cautam printre nodurile din stanga un nod care nu are inca pereche
for(int i = 1; i <= m_number_of_left_nodes; i++){
//testam daca nodul are pereche
if(right_pair[i] == -1){
//incercam sa creem un lant din acest nod fara pereche;
if(this->DFS(i,left_pair,right_pair, visited)){
//daca am reusit, atunci marcam ca am gasit un lant
enough = 0;
}
}
}
}
//formam cuplajul-rezultat: pentru toate nodurile care au pereche in dreapta, inseamna ca fac parte din cuplaj asa ca le adaugam in vectorul de perechi
//impreuna cu perechea lor din dreapta
for(int i = 1; i <= m_number_of_left_nodes; i++){
if(right_pair[i] != -1){
maximum_matching.push_back(make_pair(i, right_pair[i]));
}
}
return maximum_matching;
}
//METODE PRIVATE ALE CLASEI DE GRAF NEORIENTAT BIPARTIT
//DFS-ul folosit in gasirea cuplajului maxim
bool Unoriented_bipartite_graph::DFS(int node, vector<int>& left_pair, vector<int>& right_pair, vector<int>& visited) {
//testam daca nodul a mai fost vizitat in cuplajul pe care incercam sa il facem
if(visited[node] != 0){
return 0;
}
//marcam nodul ca vizitat
visited[node] = 1;
//parcurgem vecinii nodului si, daca gasim printre ei unul care nu are pereche in stanga, il unim cu nodul nostru
for(int i = 0; i < m_adjacency_list[node].size(); i++){
int neighbor;
//luam vecinul
neighbor = m_adjacency_list[node][i];
//verificam daca nodul nu are pereche in stanga
if(left_pair[neighbor] == -1){
//daca vecinul nu are deja pereche in stanga, il cuplam cu nodul nostru din stanga, marcandu-le amandorura noua pereche in vectorul corespunzator fiecaruia
right_pair[node] = neighbor;
left_pair[neighbor] = node;
//returnam 1 pentru ca am avut succes in a construi un nou lant din nodul dat
return 1;
}
}
//daca nu am gasit niciun vecin care sa nu aiba pereche in stanga, inseamna ca e posibil sa trebuiasca sa legam nodul de un lant deja existent, nu doar de un alt nod
//parcurgem vecinii si, daca gasim un vecin din care avem un lant, sudam nodul nostru de lantul respectiv, prin cuplarea nodului cu vecinul din care porneste lantul
for(int i = 0; i < m_adjacency_list[node].size(); i++){
int neighbor;
//luam vecinul
neighbor = m_adjacency_list[node][i];
//verificam daca vecinul face parte dintr-un lant
if(DFS(left_pair[neighbor],left_pair, right_pair, visited)){
//in cazul in care DFS a returnat 1 si vecinul face parte dintr-un lant, alipim nodul nostru la lantul respectiv <=> cuplam nodul nostru cu vecinul
//si returnam 1 pentru ca am reusit sa obtinem un lant
left_pair[neighbor] = node;
right_pair[node] = neighbor;
return 1;
}
}
//returnam esecul: nu mai putem forma lant din nodul dat in niciun fel
return 0;
}
//CLASA GRAF NEOIENTAT CU COSTURI
class Undirected_graph_with_costs: protected Undirected_graph{
private:
vector< vector<int> > m_costs_matrix;
public:
//CONSTRUCTORI
//constructor cu 3 parametri: numarul de noduri, lista de adiacenta si matricea de costuri
Undirected_graph_with_costs(int number_of_nodes, const vector< vector<int> > &adjacency_list, const vector< vector<int> > &costs_matrix);
//constructor cu 2 parametri: listele de adiacenta si matricea de costuri
Undirected_graph_with_costs(const vector<vector<int>> &adjacency_list, const vector<vector<int>> &costs_matrix);
//ALGORITMI
//algoritmul lui prim->returneaza arborele partial de cost minim si, prin parametrul primit, returneaza si costul
vector< pair<int,int> > prim(int& cost_APM);
private:
//introducerea unui node in APM
void introduce_in_APM(int node, vector<int>& distances, vector<int>& neighbors);
//introducerea unui node in heap-ul de minim
void introduce_in_min_heap(int node, vector<int>& heap, vector<int>& positions, vector<int> distances);
//urcarea in heap-ul de minim
void pop(int index, vector<int>& heap, vector<int>& poz, vector<int>& distances);
//extragerea unui node din heap-ul de minim
int extract_root_min_heap(vector<int>& heap,vector<int>& poz, vector<int> distances);
//coborarea in heap-ul de minim
void push(int index, vector<int>& heap, vector<int>& poz, vector<int>& distances);
};
//METODE PUBLICE ALE CLASEI DE GRAFURI NEORIENTATE CU COSTURI
//CONSTRUCTORI
//constructor cu 3 parametri: numarul de noduri, matricea de vecini si matricea de costuri
Undirected_graph_with_costs::Undirected_graph_with_costs(int number_of_nodes, const vector<vector<int>> &adjacency_list,
const vector<vector<int>> &costs_matrix) : Undirected_graph(
number_of_nodes, adjacency_list), m_costs_matrix(costs_matrix) {}
//constructor cu 2 parametri: matricea de vecini si matricea de costuri
Undirected_graph_with_costs::Undirected_graph_with_costs(const vector<vector<int>> &adjacency_list,
const vector<vector<int>> &costs_matrix) : Undirected_graph(adjacency_list), m_costs_matrix(costs_matrix){
m_number_of_nodes = costs_matrix.size();
}
//ALGORITMI
//ALGORITMUL LUI PRIM: O(m * log n), unde m este numarul de muchii si n este numarul de noduri
vector< pair<int,int> >Undirected_graph_with_costs::prim(int &cost_APM) {
vector<pair<int,int>> APM_edges;
vector<int> vec;
vector<int> positions;
vector<int> distances;
vector<int> heap;
//initializam vectorul de distante cu infinit pentru fiecare node, vectorul de vecini ai fiecarui node cu 0, vectorul de pozitii al fiecarui node in heap cu 0
// si heap-ul in care vom pune nodurile
distances.assign(this->m_number_of_nodes + 1, 200000200);
vec.assign(this->m_number_of_nodes + 1, 0);
positions.assign(this->m_number_of_nodes + 1, 0);
heap.push_back(0);
//pornim de la primul node: initial distanta pana la primul node este 0; introducem nodul in APM;
distances[1] = 0;
introduce_in_APM(1, distances, vec);
//luam toate nodurile si le introducem in heap-ul de minim; practic, radacina heap-ului va fi
for(int i = 2; i <= this->m_number_of_nodes; i++){
introduce_in_min_heap(i, heap, positions, distances);
}
//pentru fiecare nod din graf, luam nodul cu distanta minima (adica radacina heap-ului de minim), il adaugam in apm, actualizam costul, adaugam muchia
//care pleaca din radacina in vectorul de muchii ale apm-ului si apoi parcurgem vecinii radacinii si scoatem vecinul din heap-ul de minim daca acesta exista
for(int i = 1; i < this->m_number_of_nodes; i++){
int root;
root = extract_root_min_heap(heap, positions, distances);
introduce_in_APM(root, distances, vec);
cost_APM = cost_APM + distances[root];
APM_edges.push_back(make_pair(root, vec[root]));
for(int j = 0; j < this->m_adjacency_list[root].size(); j++){
int nod;
nod = this->m_adjacency_list[root][j];
if(positions[nod]) pop(positions[nod], heap, positions, distances);
}
}
return APM_edges;
}
//METODE PRIVATE UNORIENTED GRAPH WITH COSTS
//introducerea unui nod in apm in algoritmul lui prim
void Undirected_graph_with_costs::introduce_in_APM(int node, vector<int>& distances, vector<int>& neighbors) {
//parcurgem vecinii nodului dat; pentru fiecare vecin, incercam sa minimizam distanta;
for(int i = 0; i < this->m_adjacency_list[node].size(); i++){
int neighbor, cost;
neighbor = this->m_adjacency_list[node][i];
cost = this->m_costs_matrix[node][i];
//incercam sa minimizam distanta catre vecinul curent: in cazul in care distanta pana la vecin stiuata pana in acest moment este mai mare decat
// distanta pe care o obtinem mergand prin muchia de la nodul nostru la vecin, atunci actualizam distanta pana la vecin cu costul muchiei
//de la nodul nostru la vecin; in cazul in care s-a intamplat acest lucru, inseamna ca noul precedent al vecinului curent este nodul nostru
//asa ca, marcam acest lucru in vectorul neighbors
distances[neighbor] = min(distances[neighbor], cost);
if(distances[neighbor] == cost) neighbors[neighbor] = node;
}
}
//introducerea unui nod in heap-ul de minim
void Undirected_graph_with_costs::introduce_in_min_heap(int node, vector<int>& heap, vector<int>& poz, vector<int> distances) {
//adaugam nodul la sfarsitul heap-ului
heap.push_back(node);
poz[node] = heap.size() - 1;
//urcam nodul in heap acolo unde ii este pozitia de drept
pop(heap.size() - 1, heap, poz, distances);
}
//eliminarea unui nod din heap-ul de minim
void Undirected_graph_with_costs::pop(int index, vector<int>& heap, vector<int>& position_in_heap, vector<int>& distances) {
//cat timp n-am ajuns la radacina heap-ului si inca nodul mai poate urca, adica distanta fata de el e mai mica decat distanta fata de tatal lui,urcam in heap
while(index > 1 && distances[ heap[index] ] < distances[ heap[index / 2] ]){
//urcarea presupune ca interschimbam in heap nodul cu tatal si pozitiile nodului si a tatalui in vectorul pozitii
swap(heap[index], heap[index / 2]);
swap(position_in_heap[ heap[index] ], position_in_heap[ heap[index / 2] ]);
index = index / 2;
}
}
//extragerea radacinii din heap-ul de minim
int Undirected_graph_with_costs::extract_root_min_heap(vector<int>& heap,vector<int>& poz, vector<int> distances) {
int root;
//luam radacina si o punem la finalul heap-ului
root = heap[1];
swap(heap[1],heap[ heap.size() - 1 ]);
swap(poz[ heap[1] ], poz[ heap[ heap.size() - 1 ] ]);
//eliminam radacina din heap
heap.pop_back();
//reparam heap-ul
push(1, heap, poz, distances);
//actualizam vectorul de pozitii cu 0 in pozitia radacinii, deoarece nodul nu mai exista in heap
poz[root] = 0;
return root;
}
//adaugarea in heap-ul de minim
void Undirected_graph_with_costs::push(int index, vector<int>& heap, vector<int>& poz, vector<int>& distances) {
//cat timp nu am ajuns la finalul heap-ului pe ramura din stanga / dreapta si cat timp nodul mai poate coborî, adică distanţa fata de nodul curent e mai mare
//decat distanta fata de fiul din stanga/dreapta
while((index * 2 <= heap.size() - 1 && distances[ heap[index] ] > distances[ heap[index * 2] ]) ||
(index * 2 + 1 <= heap.size() - 1 && distances[ heap[index] ] > distances[ heap[index * 2 + 1] ])){
//comparam cei 2 fii si mergem pe cel spre care distanta e mai mica si interschimbam nodul cu fiul corespunzator
if(distances[heap[index * 2]] < distances[heap[index * 2 + 1]] || index * 2 + 1 > heap.size() - 1){
swap(heap[index], heap[index * 2]);
swap(poz[heap[index]], poz[heap[index * 2]]);
index = index * 2;
}else{
swap(heap[index], heap[index * 2 + 1]);
swap(poz[heap[index]], poz[heap[index * 2 + 1]]);
index = index * 2 + 1;
}
}
}
//CLASA GRAF ORIENTAT FARA COSTURI
class Directed_graph: protected Graph{
public:
//CONSTRUCTORI
//constructor cu 2 parametri: numarul de noduri si matricea de vecini
Directed_graph(int number_of_nodes, const vector< vector<int> > &adjacency_list);
//constructor cu 1 parametruL numarul de noduri
Directed_graph(int number_of_nodes);
//constructor cu 1 parametru: matricea de vecini
Directed_graph(const vector< vector<int> > &adjacency_list);
//ALGORITMI
//generarea componentelor tare conexe -> returneaza un vector in care pe fiecare pozitie avem un alt vector cu nodurile dintr-o componenta conexa
vector<vector<int>> create_strongly_connected_components();
//tarjan -> gasirea componentelor tare conexe
void tarjan(int node,stack<int>& current_component_stack,vector<int>& is_in_stack,vector<int>& arrival_values, int& current_arrival_value, vector<int>& low_link_values, vector<vector<int>>& strongly_connected_components);
//returnarea sortarii topologice
stack<int> topological_sort();
private:
//DFS-ul folosit in sortarea topologica
void DFS_topological_sort(int node, stack<int>& sort, vector<int>& visited);
};
//METODE PUBLICE ALE CLASEI DE GRAFURI ORIENTATE FARA COSTURI
//CONSTRUCTORI
//constructor cu 2 parametri: numarul de noduri si matricea de adiacenta
Directed_graph::Directed_graph(int number_of_nodes, const vector< vector<int> > &adjacency_list) : Graph(number_of_nodes, adjacency_list) {}
//constructor cu 1 parametru: numarul de noduri
Directed_graph::Directed_graph(int number_of_nodes) : Graph(number_of_nodes) {}
//constructor cu 1 parametru: matricea de vecini
Directed_graph::Directed_graph(const vector<vector<int>> &adjacency_list) : Graph(adjacency_list) {}
//ALGORITMI
//GASIREA COMPONENTELOR TARE CONEXE
vector< vector<int> >Directed_graph::create_strongly_connected_components() {
vector<vector<int>> strongly_connected_components;
//initializam stiva in care vom retine componenta tare conexa curenta pe care o formam; aceasta va ajunge dupa in vectorul de componente tare conexe
stack<int> current_component;
//initializam timpul de ajungere; initial 0
int current_arrival_time = 0;
//initializam vectorul care retine pe fiecare pozitie i 0 daca nodul i este in stva cu componenta tare conexa curenta si 0 daca nodul i nu este in ea
vector<int> is_in_stack;
is_in_stack.assign(this->m_number_of_nodes + 1, 0);
//initializam vectorul cu timpii de ajungere la fiecare nod: initial -1 pentru ca nu am vizitat niciun nod inca
vector<int> arrival_values;
arrival_values.assign(this->m_number_of_nodes + 1, -1);
//rezervam loc pentru vectorul care retine pe pozitia i cel mai de sus nivel la care se poate ajunge din i
vector<int> low_link_values;
low_link_values.resize(this->m_number_of_nodes + 1);
//parcurgem nodurile grafului si, pentru fiecare nod care nu a fost inca vizitat(deci timpul de ajungere la el este -1) facem tarjan
for(int i=1; i<=this->m_number_of_nodes; i++){
if(arrival_values[i] == -1){
tarjan(i, current_component, is_in_stack, arrival_values, current_arrival_time, low_link_values, strongly_connected_components);
}
}
return strongly_connected_components;
}
//TARJAN: O(numar de noduri + numar de muchii)
void Directed_graph::tarjan(int node, stack<int> ¤t_component_stack, vector<int> &is_in_stack,
vector<int> &arrival_values, int ¤t_arrival_value, vector<int> &low_link_values,
vector<vector<int>> &strongly_connected_components) {
//adaugam nodul in componenta tare conexa curenta, adica in current_component_stack
current_component_stack.push(node);
//marcam nodul ca facand parte din componenta tare conexa curenta prin vectorul is_in_stack
is_in_stack[node] = 1;
//marcam nodul ca vizitat, atribuindu-i chiar timpul de ajungere
arrival_values[node] = current_arrival_value;
//valoarea low Link momentan este tot nivelul nodului curent
low_link_values[node] = current_arrival_value;
//marim timpul de ajungere pentru urmatorul step
current_arrival_value++;
//parcurgem vecinii nodului curent, facand un DFS
for(int i=0; i<this->m_adjacency_list[node].size(); i++){
int neighbor = this->m_adjacency_list[node][i];
//verificam daca vecinul curent nu a fost inca vizitat
if(arrival_values[neighbor] == -1){
//aplicam tarjan pe nodul curent
tarjan(neighbor, current_component_stack, is_in_stack, arrival_values, current_arrival_value, low_link_values, strongly_connected_components);
//la iesire incercam sa minimizam valoarea low link a nodului curent, daca vecinul la care suntem a facut in timpul tarjan-ului una mai mica
if(low_link_values[neighbor] < low_link_values[node]){
low_link_values[node] = low_link_values[neighbor];
}
}else{ //daca vecinul a fost deja vizitat
//verificam daca vizitarea s-a produs in cadrul componentei tare conexe curente
if(is_in_stack[neighbor] == 1){
//incercam sa minimizam valoarea low link a nodului curent, in cazul in care vecinul curent ajunge la un node mai indepartat decat valoarea noastra curenta
if(low_link_values[neighbor] < low_link_values[node]){
low_link_values[node] = low_link_values[neighbor];
}
}
}
}
//verificam daca nodul curent inchide o componenta tare conexa
if(arrival_values[node] == low_link_values[node]){
//trebuie sa mutam componenta tare conexa curenta din stiva in vectorul cu toate componentele tare conexe din graf
vector<int> aux;
int aux_node;
do{
aux_node = current_component_stack.top();
aux.push_back(aux_node);
current_component_stack.pop();
is_in_stack[aux_node] = 0;
}while(aux_node != node);
strongly_connected_components.push_back(aux);
}
}
//SORTAREA TOPOLOGICA: O(numar noduri + numar de muchii)
stack<int> Directed_graph::topological_sort() {
vector<int> visited;
stack<int> sort;
//initial toate nodurile sunt nevizitate
visited.assign(m_number_of_nodes + 1, 0);
//parcurgem toate nodurile grafului si, pentru fiecare nod nevizitat inca, aplicam DFS
for(int i = 1; i <= this->m_number_of_nodes; i++){
if(visited[i] == 0){
DFS_topological_sort(i, sort, visited);
}
}
return sort;
}
//METODE PRIVATE ORIENTED GRAPHS
//DFS-ul pe care il folosim in sortarea topologica
void Directed_graph::DFS_topological_sort(int node, stack<int> &sort, vector<int>& visited) {
//marcam nodul la care am ajuns ca vizitat
visited[node] = 1;
//parcurgem vecinii nodului curent si, daca vecinul este nevizitat, ii aplicam DFS
for(int i = 0; i < this->m_adjacency_list[node].size(); i++){
int neighbor = this->m_adjacency_list[node][i];
if(visited[neighbor] == 0){
DFS_topological_sort(neighbor, sort, visited);
}
}
//adaugam nodul curent in stiva care retine nodurile pe masura ce ajungem la ele
sort.push(node);
}
//CLASA GRAF ORIENTAT CU COSTURI
class Directed_graph_with_costs: protected Directed_graph{
private:
vector< vector<int> > m_costs_matrix;
public:
//CONSTRUCTORI
//constructor cu 3 parametri: numarul de noduri, lista de adiacenta si matricea de costuri
Directed_graph_with_costs(int number_of_nodes, const vector< vector<int> > &adjacency_list, const vector< vector<int> > &costs_matrix);
//constructor cu 2 parametri: listele de adiacenta si matricea de costuri
Directed_graph_with_costs(const vector<vector<int>> &adjacency_list, const vector<vector<int>> &costs_matrix);
//ALGORITMI
//getter pentru matricea de costuri
vector< vector<int> > get_costs_matrix();
//metoda dijkstra -> returneaza un vector in care pe fiecare pozitie i este distanta minima de la nodul dat ca argument la nodul i
vector<int> dijkstra(int source);
//metoda bellman-ford fara argumente -> returneaza matricea de drumuri din matricea de costuri a grafului
vector< vector<int> > bellman_ford();
//metoda bellman-ford cu argumente -> primeste matricea de costuri si returneaza matricea de drumuri
vector< vector<int> > bellman_ford(vector< vector<int> > costs_matrix);
//metoda hamilton -> returneaza costul ciclului hamiltonian de cost minim; daca graful nu este hamiltonian, returneaza -1
int hamilton();
};
//METODE PUBLICE ALE CLASEI DE GRAFURI ORIENTATE CU COSTURI
//CONSTRUCTORI
//constructor cu 3 parametri: numarul de noduri, matricea de vecini si matricea de costuri
Directed_graph_with_costs::Directed_graph_with_costs(int number_of_nodes, const vector<vector<int>> &adjacency_list,
const vector<vector<int>> &costs_matrix) : Directed_graph(
number_of_nodes, adjacency_list), m_costs_matrix(costs_matrix) {}
//constructor cu 2 parametri: matricea de vecini si matricea de costuri
Directed_graph_with_costs::Directed_graph_with_costs(const vector<vector<int>> &adjacency_list,
const vector<vector<int>> &costs_matrix) : Directed_graph(adjacency_list), m_costs_matrix(costs_matrix){
m_number_of_nodes = costs_matrix.size();
}
//ALGORITMI
//getter-ul pentru matricea de costuri
vector< vector<int> > Directed_graph_with_costs::get_costs_matrix() {
return this->m_costs_matrix;
}
vector<int> Directed_graph_with_costs::dijkstra(int source) {
vector<int> paths;
//initializam vectorul de distante minime cu infinit pe fiecare pozitie corepsunzatoare fiecarui node
paths.assign(this->m_number_of_nodes + 1, 200000200);
//pornim de la nodul dat ca argument: paths[nodul surs] = 0: distanta de la nodul sursa la el insusi este 0
paths[source] = 0;
//tree este un arbore care retine perechi de forma (cost de a ajunge de la nodul sursa la nodul i, nodul i);
// introducem in arbore prima pereche: distanta de la nodul sursa la acesta(adica 0) si nodul sursa
set<pair<int,int>> tree;
tree.insert(make_pair(0, source));
//cat timp arborele nu e gol
while(!tree.empty()){
//extragem din arbore nodul si costul de la radacina
int nod,cost;
nod = tree.begin()->second;
cost = tree.begin()->first;
tree.erase(tree.begin());
//parcurgem vecinii nodului de la radacina arborelui si incercam minimizarea distantelor
for(int i = 0; i < this->m_adjacency_list[nod].size(); i++){
int neighbor, cost_neighbor;
neighbor = this->m_adjacency_list[nod][i];
cost_neighbor = this->m_costs_matrix[nod][i];
//daca distanta de la nodul sursa pana la vecin pe care o aveam pana la acest moment este mai mare decat
//distanta pe care am obtine-o prin nodul curent cu drumul pana la acesta + costul muchiei de la acesta la vecin
//atunci minimizam distanta catre vecin; in cazul in care este primul drum pe care il gasim catre vecin, scoatem din arbore perechea corespunzatoare vecinului
if(paths[neighbor] > paths[nod] + cost_neighbor){
if(paths[neighbor] != 200000200){
tree.erase(tree.find(make_pair(paths[neighbor], neighbor)));
}
paths[neighbor] = paths[nod] + cost_neighbor;
//adaugam in arbore perechea data de vecin si costul drumului pana la acesta
tree.insert(make_pair(paths[neighbor], neighbor));
}
}
}
//pentru nodurile pentru care distanta de la nodul sursa la ele a ramas infinit, inseamna ca nu exista drum de la nodul sursa la acetea;
//asadar, trebuie sa modificam in vectorul cu distante minim aceste valori cu 0;
for(int i = 1; i <= this->m_number_of_nodes; i++){
if(paths[i] == 200000200) paths[i] = 0;
}
return paths;
}
//bellman-ford fara matricea data
vector< vector<int> > Directed_graph_with_costs::bellman_ford() {
vector<vector<int>> path_matrix;
vector<int> aux;
//initializam matricea de drumuri cu numarul de noduri ale grafului nostru
aux.assign(this->m_number_of_nodes + 1, 0);
path_matrix.assign(this->m_number_of_nodes + 1, aux);
//initial, pe fiecare pozitie (i, j) in matricea de drumuri se afla costul de a ajunge de la i la j prin muchia directa;
for(int i = 1; i <= this->m_number_of_nodes; i++){
for(int j = 1; j <= this->m_number_of_nodes; j++){
path_matrix[i][j] = this->m_costs_matrix[i][j];
}
}
for(int k = 1; k <= this->m_number_of_nodes; k++){
for(int i = 1; i <= this->m_number_of_nodes; i++){
for(int j = 1; j <= this->m_number_of_nodes; j++){
if(i != j && path_matrix[i][k] != 0 && path_matrix[k][j] != 0){
if(path_matrix[i][j] > path_matrix[i][k] + path_matrix[k][j]){
path_matrix[i][j] = path_matrix[i][k] + path_matrix[k][j];
}else if (path_matrix[i][j] == 0){
path_matrix[i][j] = path_matrix[i][k] + path_matrix[k][j];
}
}
}
}
}
return path_matrix;
}
//bellman-ford cu matricea data
vector< vector<int> > Directed_graph_with_costs::bellman_ford(vector<vector<int>> costs_matrix) {
vector<vector<int>> path_matrix;
vector<int> aux;
//initializam matricea de drumuri cu numarul de noduri ale grafului nostru
aux.assign(this->m_number_of_nodes + 1, 0);
path_matrix.assign(this->m_number_of_nodes + 1, aux);
//initial, pe fiecare pozitie (i, j) in matricea de drumuri se afla costul de a ajunge de la i la j prin muchia directa;
for(int i = 1; i <= this->m_number_of_nodes; i++){
for(int j = 1; j <= this->m_number_of_nodes; j++){
path_matrix[i][j] = costs_matrix[i][j];
}
}
for(int k = 1; k <= this->m_number_of_nodes; k++){
for(int i = 1; i <= this->m_number_of_nodes; i++){
for(int j = 1; j <= this->m_number_of_nodes; j++){
if(i != j && path_matrix[i][k] != 0 && path_matrix[k][j] != 0){
if(path_matrix[i][j] > path_matrix[i][k] + path_matrix[k][j]){
path_matrix[i][j] = path_matrix[i][k] + path_matrix[k][j];
}else if (path_matrix[i][j] == 0){
path_matrix[i][j] = path_matrix[i][k] + path_matrix[k][j];
}
}
}
}
}
return path_matrix;
}
//hamilton() returneaza costul ciclului hamiltonian minim, sau -1 daca graful nostru nu este hamiltonian
int Directed_graph_with_costs::hamilton() {
vector< vector<int> > minimum_costs;
vector<int> aux;
//initializam matricea cu costuri minime ale drumurilor de la un nod la altul -> avem atatea linii
// cate variante de drumuri putem avea, adica atatea linii cate numere in baza 2 cu nr_noduri cifre putem scrie.
// avem atatea coloane cate noduri sunt
aux.assign(m_number_of_nodes + 1, 100000000);
minimum_costs.assign(1 << m_number_of_nodes, aux);
//initializam lantul format dintr-un singur nod cu cost 0
minimum_costs[1][0] = 0;
//formam matricea costurilor minime posibile ale tuturor drumurilor posibile - parcurgem toate drumurile posibile si,
//pentru fiecare nod, verificam daca acel nod se afla in drumul curent sau nu, caz in care trebuie sa actualizam costul minim al lantului
//care ajunge in acel nod
for(int i = 0; i < 1 << m_number_of_nodes; i++){
for(int j = 0; j < m_number_of_nodes; j++){
//pentru fiecare drum, parcurgem toate nodurile grafului si, pentru nodurile care fac parte din drum, incercam sa actualizam costurile minime ale drumurilor pana la j prin i
//i este drumul; j este nodul; daca j face parte din i, atunci bitul de pe pozitia j din i este 1
if( i & (1 << j) ){
//daca nodul j face parte din drumul curent i, parcurgem vecinii nodului j si, daca vecinul face parte si el din drum, atunci incercam sa actualizam costul minim al drumului
//pana la nodul j prin drumul i
for(int k = 0; k < m_adjacency_list[j].size(); k++){
if( i & (1 << m_adjacency_list[j][k]) ){
//daca vecinul nodului apartine drumului, verificam daca e cazul sa actualizam minimul costurilor drumurilor pana la nodul j prin drumul i
//cu suma dintre costul minim pana la vecin + costul muchiei de la vecin la j
minimum_costs[i][j] = min( minimum_costs[i][j], minimum_costs[i ^ (1 << j) ][ m_adjacency_list[j][k] ] + m_costs_matrix[ m_adjacency_list[j][k] ][j]);
}
}
}
}
}
//aflam costul minim al unnui ciclu
int mini = 100000000;
for(int i = 0; i < m_adjacency_list[0].size(); i++){
mini = min(mini, minimum_costs[ (1 << m_number_of_nodes) - 1 ][ m_adjacency_list[0][i] ] + m_costs_matrix[ m_adjacency_list[0][i] ][0]);
}
//daca mini a ramas infinit, inseamna ca graful nu este hamiltonian
if(mini == 100000000) return -1;
return mini;
}
//CLASA ARBORE
class Tree: protected Graph{
private:
//vectorul de tati
vector<int> m_fathers_array;
//vectorul de ranguri
vector<int> m_ranks_array;
public:
//CONSTRUCTORI
//constructor cu 2 parametri: numarul de noduri si listele de adiacenta
Tree(int number_of_node, const vector< vector<int> >& adjacency_list);
//constructor cu 4 parametri: numarul de noduri, listele de adiacenta, vectorul de tati si vectorul de ranguri
Tree(int number_of_nodes, const vector<vector<int>> &adjacency_list, const vector<int> &fathers_array, const vector<int> &ranks_array);
//ALGORITMI
//BFS pentru diametrul arborelui
void BFS(int node, int& diameter, int& last);
//initializarea vectorului de tati
void initialize_fathers_array();
//initializarea vectorului de ranguri
void initialize_ranks_array(int value);
//setter pentru numarul de noduri
void set_number_of_nodes(int number_of_nodes);
//gasirea unui nod intr-un arbore -> returneaza numarul multimii in care se afla (identificat prin nodul radacina al arborelui ce reprezinta multimea)
int find(int node);
//reuninea a 2 multimi in arbore -> primeste ca argument numerele multimilor ce trebuie reunite (adica nodurile radacina ale celor 2 arbori ce reprezinta multimile)
void unify(int set1, int set2);
};
//METODE PUBLICE ALE CLASEI ARBORE
//CONSTRUCTORI
//constructor cu 2 parametri: numarul de noduri si listele de adiacenta
Tree::Tree(int number_of_node, const vector<vector<int>> &adjacency_list) : Graph(number_of_node, adjacency_list){
m_fathers_array.assign(m_number_of_nodes + 1, 0);
m_fathers_array.assign(m_number_of_nodes + 1, -1);
}
//constructor cu 4 parametri: numarul de noduri, listele de adiacenta, vectorul de tati si vectorul de ranguri
Tree::Tree(int number_of_nodes, const vector<vector<int>> &adjacency_list, const vector<int> &fathers_array,
const vector<int> &ranks_array) : Graph(number_of_nodes, adjacency_list), m_fathers_array(fathers_array), m_ranks_array(ranks_array) {}
//ALGORITMI
void Tree::BFS(int node, int &diameter, int &last) {
//initializam vectorul de distances minime
vector<int> distances;
distances.assign(this->m_number_of_nodes + 1, 0);
int current_node;
//in nodes_queue vom pune nodurile pe massura ce le parcurgem
queue<int> nodes_queue;
//initial toate nodurile sunt nevizitate, asaa ca initializam visited[orice node] = 0
vector<int> visited;
visited.assign(this->m_number_of_nodes + 1, 0);
//adaugam nodul sursa in nodes_queue si il marcam ca si vizitat
nodes_queue.push(node);
visited[node] = 1;
//actualizam vectorul de distances pentru nodul current_node cu distanta pana la el, adica 1
distances[node] = distances[node] + 1;
//facem BFS-ul
while(!nodes_queue.empty()){
current_node = nodes_queue.front();
//parcurgem vecinii nodului current_node si pe fiecare vecin nevizitat il adaugam in nodes_queue, ii actualizam distanta pana la el si il marcam ca si vizitat
for(int i=0; i < this->m_adjacency_list[current_node].size(); i++){
if(visited[this->m_adjacency_list[current_node][i]] == 0){
nodes_queue.push(this->m_adjacency_list[current_node][i]);
distances[nodes_queue.back()] = distances[current_node] + 1;
visited[this->m_adjacency_list[current_node][i]] = 1;
diameter = distances[this->m_adjacency_list[current_node][i]];
last = this->m_adjacency_list[current_node][i];
}
}
//am terminat cu nodul current_node, il scoatem din nodes_queue
nodes_queue.pop();
}
}
//initializarea vectorilor de tati cu valoarea nodului de pe fiecare pozitie
void Tree::initialize_fathers_array() {
if(m_fathers_array.size() <= m_number_of_nodes) m_fathers_array.resize(m_number_of_nodes + 1);
for(int i = 1; i <= m_number_of_nodes; i++){
m_fathers_array[i] = i;
}
}
void Tree::initialize_ranks_array(int value) {
m_ranks_array.assign(m_number_of_nodes + 1, value);
}
void Tree::set_number_of_nodes(int number_of_nodes) {
m_number_of_nodes = number_of_nodes;
m_fathers_array.resize(m_number_of_nodes + 1);
m_ranks_array.resize(m_number_of_nodes + 1);
}
//gasirea multimii din care face parte un element: O(log n), unde n este numarul de noduri ale arborelui
int Tree::find(int node) {
int root;
//gasesc radacina arborelui din care face parte nodul dat <=> pornesc din nodul dat si urc in arbore pana gasesc nodul care pointeaza catre el insusi
root = node;
while(m_fathers_array[root] != root){
root = m_fathers_array[root];
}
//facem compresia durmurilor, pentru a scadea timpul de executie
//acum ca stim unde se afla nodul x, urcam din tata in tata pana la radacina si il legam pe fiecare nod prin care trecem de radacina
//astfel, cand vom avea urmatoarea interogare, avem nodul cautat direct legat de radacina, asa ca vom putea raspunde in O(1)
do{
int aux;
aux = m_fathers_array[node];
m_fathers_array[node] = root;
node = aux;
}while(m_fathers_array[node] != node);
return root;
}
//reunirea a 2 multimi: O(1)
void Tree::unify(int set1, int set2) {
//multimea cu rang mai mic va deveni surbaroe al celei cu rang mai mare <=> tatal radacinii multimii cu rangul mai mic devine radacina celei cu rangul mai mare
if(m_ranks_array[set1] > m_ranks_array[set2]) m_fathers_array[set2] = set1;
else m_fathers_array[set1] = set2;
//daca ambele multimi au acelasi rang, inseamna ca multime-mama a devenit a doua, deci ii cresc rangul
if(m_ranks_array[set1] == m_ranks_array[set2]) m_ranks_array[set2]++;
}
//CLASA RETELE DE TRANSPORT
class Flow_network: Directed_graph{
private:
vector< vector<int> > m_capacities_matrix;
public:
//CONSTRUCTORI
//constructor cu 3 parametri: numarul de noduri, lista de adiacenta si matricea de costuri
Flow_network(int number_of_nodes, const vector< vector<int> > &adjacency_list, const vector< vector<int> > &capacities_matrix);
//constructor cu 2 parametri: listele de adiacenta si matricea de costuri
Flow_network(const vector<vector<int>> &adjacency_list, const vector<vector<int>> &capacities_matrix);
//ALGORITMI
//metoda edmonds_karp() -> returneaza fluxul maxim care poate fi transportat
int edmonds_karp();
private:
//BFS-ul folosit in gasirea flucului maxim in edmonds_karp()
int BFS(vector<int>& father, vector< vector<int> >& f, vector<int>& visited);
};
//METODE PUBLICE ALE CLASEI DE FLUXURI DE TRANSPORT
//CONSTRUCTORI
//constructor cu 3 parametri: numarul de noduri, matricea de vecini si matricea de costuri
Flow_network::Flow_network(int number_of_nodes, const vector<vector<int>> &adjacency_list,
const vector<vector<int>> &capacities_matrix) : Directed_graph(
number_of_nodes, adjacency_list), m_capacities_matrix(capacities_matrix) {}
//constructor cu 2 parametri: matricea de vecini si matricea de costuri
Flow_network::Flow_network(const vector<vector<int>> &adjacency_list,
const vector<vector<int>> &capacities_matrix) : Directed_graph(adjacency_list), m_capacities_matrix(capacities_matrix){
m_number_of_nodes = capacities_matrix.size();
}
int Flow_network::edmonds_karp() {
//initializam flow-ul maxim cu 0
int flow = 0;
vector<int> father;
vector< vector<int> > f;
vector<int> visited;
//initializam vectorul de tati pentru fiecare nod cu 0
father.assign(m_number_of_nodes + 1, 0);
//initializam vectorul de fluxuri pentru fiecare nod cu un vector gol
f.assign(m_number_of_nodes + 1, vector<int>());
//cat timp nu am atins ultimul nod
while(BFS(father,f,visited)){
//parcurgem vecinii ultimului nod
for(int i = 0; i < m_adjacency_list[m_number_of_nodes].size(); i++){
int node;
node = m_adjacency_list[m_number_of_nodes][i];
//pentru fiecare vecin, verificam daca fluxul de la vecinul ultimului nod la ultimul nod din matricea de fluxuri este diferit
//de capacitatea de a ajunge de la vecin la ultimul nod din matricea de capacitati; daca cele 2 sunt diferite si vecinul nu a fost inca vizitat
//inseamna ca putem conecta vecinul la flux
if(f[node][m_number_of_nodes] != m_capacities_matrix[node][m_number_of_nodes] && visited[node] != 0) {
//conectam vecinul la flux
father[m_number_of_nodes] = node;
int fmin = 1000000;
//urcam pe arbore din tata in tata si cautam diferenta minima intre capacitatea si fluxul de la tata nodului la nod(care este vecinul pe care il adaugam la flux)
for (node = m_number_of_nodes; node != 1; node = father[node]) {
fmin = min(fmin, m_capacities_matrix[father[node]][node] - f[father[node]][node]);
}
//daca exista o diferenta intre capacitate si flux, atunci actualizam fluxul din tata in tata in tatal vecinului
if (fmin != 0) {
for (node = m_number_of_nodes; node != 1; node = father[node]) {
f[father[node]][node] = f[father[node]][node] + fmin;
f[node][father[node]] = f[node][father[node]] - fmin;
}
//actualizam rezultatul fluxului final cu fluxul pe care l-am adaugat
flow = flow + fmin;
}
}
}
}
return flow;
}
//METODE PRIVATE RETEA DE TRANSPORT
//BFS-ul pe care il folosim la edmonds_karp() la aflarea fluxului maxim
int Flow_network::BFS(vector<int>& father, vector< vector<int> >& f, vector<int>& visited) {
vector<int> cd;
//initializam vectorul cd pentru maxim 1024 de noduri (el este coada tipica din BFS)
cd.assign(1024,0);
//in cd[0] vom retine numarul nodurilor din vectorul cd; initial avem doar nodul 1
cd[0] = cd[1] = 1;
//initializam vectorul de noduri vizitate
visited.assign(m_number_of_nodes + 1, 0);
//marcam primul nod ca vizitat
visited[1] = 1;
//parcurgem nodurile din cd
for(int i = 1; i <= cd[0]; i++){
int node;
node = cd[i];
//daca nodul nostru nu este ultimul nod, atunci ii parcurgem vecinii si incercam sa gasim un vecin nevizitat la care fluxul difera de capacitate
if(node != m_number_of_nodes) {
for (int j = 0; j < m_adjacency_list[node].size(); j++) {
int neighbor;
neighbor = m_adjacency_list[node][j];
//daca vecinul nostru este nevizitat si fluxul de la nodul nostru din cd la vecin este diferit de capacitatea de la nodul nostru la vecin,
//atunci il marcam ca si vizitat, il adaugam in cd si facem optimizare in arbore: marcam tatal vecinului direct nodul nostru
if (m_capacities_matrix[node][neighbor] != f[node][neighbor] && visited[neighbor] == 0) {
visited[neighbor] = 1;
cd[++cd[0]] = neighbor;
father[neighbor] = node;
}
}
}
}
//returnam daca prin BFS s-a ajuns la ultimul nod sau nu
return visited[m_number_of_nodes];
}
//CLASA MULTIGRAF
class Multigraph:Graph{
private:
vector< vector<int> > m_nodes_edges;
vector< pair<int,int> > m_edges;
public:
//CONSTRUCTORI
//constructor cu 3 argumente: numarul de noduri, vectorii de muchii
Multigraph(int numberOfNodes, const vector<vector<int>> &mNodesEdges, const vector<pair<int, int>> &mEdges);
//euler(nod) -> determina un ciclu eulerian din multigraf si il returneaza, sau returneaza -1 daca graful nu are niciun ciclu eulerian
vector<int> euler(int nod);
private:
//verificarea daca toate nodurile multigrafului au grad par
bool check_even_degrees();
};
//METODE PUBLICE MULTIGRAF
vector<int> Multigraph::euler(int nod) {
vector<int> euler_cycle;
//una din conditiile ca un graf sa fie eulerian este sa aiba toate nodurile cu graduri pare, asa ca testam acest lucru
if(!this->check_even_degrees()){
euler_cycle.push_back(-1);
return euler_cycle;
}
stack<int> nodes;
vector<int> visited_edges;
//initializam vectorul de muchii vizitate: initial toate sunt nevizitate
visited_edges.assign(m_edges.size(), 0);
//adaugam in stiva cu ciclul format momentan primul nod: cel dat
nodes.push(nod);
//cat timp stiva nu e goala <=> cat timp mai avem noduri in ciclul format
while(!nodes.empty()){
//preluam nodul curent din ciclul format
int current_node;
current_node = nodes.top();
//daca nodul curent are vecini, luam muchia catre un vecin aleator al nodul curent - aici ultimul, pentru a-l putea elimina usor
if(m_nodes_edges[current_node].size() != 0){
int random_edge;
random_edge = m_nodes_edges[current_node].back();
//eliminam muchia aleasa
m_nodes_edges[current_node].pop_back();
//daca muchia nu a mai fost vizitata pana acum, atunci luam muchia care pleaca din el si adaugam nodul destinatie in stiva cu ciclul format
if(visited_edges[random_edge] == 0){
//marcam muchia ca vizitata
visited_edges[random_edge] = 1;
//adaugam vecinul la care ne trimite muchia in stiva cu ciclul eulerian curent
nodes.push(m_edges[random_edge].first ^ m_edges[random_edge].second ^ current_node);
}
} else {
//daca nodul curent nu are vecini, il scoatem din stiva cu ciclul eulerian format si il adaugam in rezultat
nodes.pop();
euler_cycle.push_back(current_node);
}
}
return euler_cycle;
}
//METODE PRIVATE MULTIGRAF
//check_even_degrees -> verifica daca toate nodurile muligrafului au grad par
bool Multigraph::check_even_degrees() {
for(int i = 1; i <= m_number_of_nodes; i++){
if(m_nodes_edges[i].size() % 2 == 1){
return false;
}
}
return true;
}
Multigraph::Multigraph(int numberOfNodes, const vector<vector<int>> &mNodesEdges, const vector<pair<int, int>> &mEdges)
: Graph(numberOfNodes), m_nodes_edges(mNodesEdges), m_edges(mEdges) {}
//HELPERE
//printarea unui vector de int-uri -> primeste ca argumente vectorul, calea catre fisier si numarul de pozitii de la inceput pe care le sarim
void print_vector(vector<int> v, char *file, int i = 0){
ofstream g(file);
vector<int>::iterator it;
for(it = v.begin() + 1 + i; it != v.end(); it++){
g << *it <<" ";
}
}
//printarea unui vector de unordered set-uri -> primeste ca argumente vectorul, calea catre fisier si numarul de pozitii de la inceput pe care le sarim
void print_vector_of_unordered_sets(vector< unordered_set<int> > v, char *file, int i = 0){
ofstream g(file);
vector< unordered_set<int> >::iterator it;
unordered_set<int>::iterator it_u;
g << v.size() << "\n";
for(it = v.begin() + i; it != v.end(); it++){
for(it_u = it->begin(); it_u != it->end(); it_u++){
g << *it_u << " ";
}
g << "\n";
}
}
//printarea unui vector de vectori de int-uri
//primeste ca argumente vectorul, calea catre fisier si numarul de pozitii de la inceput pe care le sarim si un bool care ne zice daca vrem sa se afiseze
//si numarul de elemente ale vectorului sau nu
void print_vector_of_vectors(vector< vector<int> >v, char *file, int i = 0, bool show_size = true){
ofstream g(file);
vector< vector<int> >::iterator it;
vector<int>::iterator it_u;
if(show_size == true) g << v.size() << "\n";
for(it = v.begin() + i; it != v.end(); it++){
for(it_u = it->begin() + i; it_u != it->end(); it_u++){
g << *it_u << " ";
}
g << "\n";
}
}
//afisarea unei stive -> primeste ca argumente vectorul si calea catre fisier
void print_stack(stack<int> s, char *file){
ofstream g(file);
while(!s.empty()){
g << s.top() << " ";
s.pop();
}
}
//citirea unui vector de int-uri -> primeste ca argumente vectorul si calea catre fisier
void read_vector(vector<int>& v, char *file){
ifstream f(file);
int size;
f >> size;
for(int i = 0; i < size; i++){
int value;
f >> value;
v.push_back(value);
}
}
//citirea unui graf neorientat fara costuri din fisier
// -> primeste ca argument calea catre un fisier care are pe prima linie numarul de noduri si numarul ne muchii
//iar apoi pe fiecare linie cate o pereche de numere reprezentand capetele fiecarei muchii din graf
//mai primeste ca si argument numarul de noduri, prin care se va returna si numarul de noduri citit
vector< vector<int> > read_undirected_graph_without_costs(char *file, int& number_of_nodes){
int number_of_edges;
vector< vector<int> > adjacency_list;
vector<int> aux;
ifstream in(file);
//citim numarul de noduri si de muchii
in >> number_of_nodes >> number_of_edges;
//initializam listele de adiacenta pentru numarul de noduri dat
aux.assign(number_of_nodes + 1, 0);
adjacency_list.assign(number_of_nodes + 1, aux);
//parcurgem muchiile si adaugam vecinii in listele de adiacenta
for(int i = 0; i < number_of_edges; i++){
int x,y;
in >> x >> y;
adjacency_list[x].push_back(y);
adjacency_list[y].push_back(x);
}
return adjacency_list;
}
//citirea unui graf orientat fara costuri din fisier
vector< vector<int> > read_directed_graph_without_costs(char *file, int& number_of_nodes){
int number_of_edges;
vector< vector<int> > adjacency_list;
vector<int> aux;
ifstream in(file);
//citim numarul de noduri si de muchii
in >> number_of_nodes >> number_of_edges;
//initializam listele de adiacenta pentru numarul de noduri dat
aux.assign(number_of_nodes + 1, 0);
adjacency_list.assign(number_of_nodes + 1, aux);
//parcurgem muchiile si adaugam vecinii in listele de adiacenta
for(int i = 0; i < number_of_edges; i++){
int x,y;
in >> x >> y;
adjacency_list[x].push_back(y);
}
return adjacency_list;
}
//HELPERE PENTRU INFOARENA
//DFS - NUMARUL DE COMPONENTE CONEXE
void solve_dfs_infoarena(){
ofstream out("../dfs.out");
int number_of_nodes = 0;
vector< vector<int> > edges;
edges = read_undirected_graph_without_costs("../dfs.in", number_of_nodes);
Undirected_graph g(number_of_nodes,edges);
int number;
//metoda number_of_connected_components() ne va returna un int cu numarul de componente conexe
number = g.number_of_connected_components();
out << number;
}
int main() {
//DFS INFOARENA
solve_dfs_infoarena();
return 0;
}
Danila Mihaela MihaelaDanila