#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <stack>
#include <set>
#include <algorithm>

using namespace std;

//CLASA DE BAZA GRAPH

class Graph{

//DATELE MEMBRE

protected:
    int m_number_of_nodes;
    //numarul de noduri


//METODELE

public:

    //CONSTRUCTORI

    //constructor cu 1 parametru: numarul de noduri
    Graph(int number_of_nodes);

    //constructor fara parametru
    Graph();

    //ALGORITMI

    //functia de citire virtuala -> implementata diferit in fiecare dintre clase
    virtual void read_graph(char *file);

    //parcurgerea in latime BFS -> primeste un nod sursa si returneaza un vector in care pe pozitia i se afla numarul minim de muchii prin care ajungem
    //de la nodul dat la nodul i
    virtual vector<int> BFS(int node);

    //parcurgerea in adancime DFS -> avem 2 implementari, una fara vectorul de noduri vizitate(si vom considera la inceput toate nodurile vizitate) 
    //si una care primeste nodul sursa si, optional, un vector cu nodurile vizitate; daca acesta nu este dat, se vor considera
    //toate nodurile nevizitate
    virtual void DFS(int node);

    virtual void DFS(int node, vector<int>& visited);

    //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);
};

//METODE PUBLICE

//CONSTRUCTORI

//constructor cu 1 parametru: numarul de noduri
Graph::Graph(int number_of_nodes){
    m_number_of_nodes = number_of_nodes;
}

//constructor fara parametru
Graph::Graph() {
    m_number_of_nodes = 0;
}

//ALGORITMI

//citirea grafului -> nu contine nimic; este virtuala si implementata diferit in fiecare dintre clasele mostenitoare
void Graph::read_graph(char *file) {
    return;
}

//parcurgerea BFS -> nu contine nimic; este tot virtuala

vector<int> Graph::BFS(int source) {
    return vector<int>();
}

//parcurgerea DFS -> tot virtuala

void Graph::DFS(int node){
    return;
}

void Graph::DFS(int node, vector<int> &visited) {
    return;
}

//algoritmul Havel Hakimi

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, cat timp nu s-a ajuns ca sa fie cel mai mare grad 0(acest lucru inseamna ca) au fost epuizate toate gradele cu succes
    while(v[0] != 0){

        //parcurgem toate nodurile si le legam cu nodul cu gradul maxim
        // (scazand gradul fiecaruia, practic ducem cate o muchie din fiecare catre nodul cu gradul maxim)
        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;
        }

        //actualizam gradul nodului al carui grad l-am epuizat; la urmatoarea sortare el va ajunge ultimul, alaturi de restul care au deja gradele epuizate
        //raman in fata cele care nu si-au epuizat inca gradul, in ordine descrescatoare
        v[0] = 0;
        sort(v.begin(), v.end(), greater<int>());
    }

    return true;
}

//CLASA GRAF NEORIENTAT

class Undirected_graph: protected Graph{
protected:
    vector< vector<int> > m_adjancency_list;
public:
    //CONSTRUCTORI

    //constructorul cu 2 parametri: numarul de noduri si lista de adiacenta
    Undirected_graph(int number_of_nodes, const vector<vector<int>> &adjacency_list);

    //constructorul fara parametri
    Undirected_graph();

    //ALGORITMI

    //citirea grafului
    void read_graph(char *file);

    //parcurgerea in adancime DFS care primeste nodul sursa doar
    void DFS(int node);

    //parcurgerea in adancime DFS care primeste nodul sursa si vectorul de noduri vizitate
    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();

    //gasirea muchiilor critice
    vector< vector<int> > find_critical_edges();

    //setter pentru numarul de noduri
    void set_number_of_nodes(int n);

    //setter pentru listele de adiacenta
    void set_adjacency_list(vector<vector<int>> adjacency_list);

private:
    //DFS-ul folosit in 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 in 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 GRAFURI NEORIENTATE

//CONSTRUCTORI

//constructorul cu 2 parametri: numarul de noduri si listele de adiacenta
Undirected_graph::Undirected_graph(int number_of_nodes, const vector<vector<int>> &adjacency_list) : Graph(
        number_of_nodes), m_adjancency_list(adjacency_list) {}

//constructorul fara parametri
Undirected_graph::Undirected_graph() {
    m_number_of_nodes = 0;
    m_adjancency_list.resize(m_number_of_nodes);
}

//ALGORITMI

//citirea grafului neorientat fara costuri
void Undirected_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);
    }
}

//parcurgerea DFS primind doar nodul sursa
void Undirected_graph::DFS(int node) {

    //pornim cu ideea ca toate nodurile sunt nevizitate initial
    vector<int> visited;
    visited.assign(m_number_of_nodes + 1, 0);

    //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);
        }
    }
}

//parcurgerea DFS primind si vectorul de noduri vizitate
void Undirected_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);
        }
    }
}

void Undirected_graph::set_number_of_nodes(int n){
    m_number_of_nodes = n;
}

void Undirected_graph::set_adjacency_list(vector< vector<int> > connections){
    m_adjancency_list.assign(m_number_of_nodes + 1, vector<int>());

    for(int i = 0 ; i < connections.size() ; i++){
        m_adjancency_list[connections[i][0]].push_back(connections[i][1]);
        m_adjancency_list[connections[i][1]].push_back(connections[i][0]);
    }
}

//numararea componentelor conexe
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 node 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;
}

//returnarea unui vector in care pe fiecare pozitie se afla o componenta biconexa
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 si nivelul cel mai de sus pentru fiecare node

    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;
}

//returnarea unui vector in care pe fiecare pozitie se afla o muchie critica
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 vectorul de noduri vizitate: initial toate nodurile grafului sunt nevizitate
    visited.assign(m_number_of_nodes + 1, 0);

    //rezervam loc pentru fiecare nod al grafului in vectorul prec, care retine pe fiecare pozitie i precedentul nodului i
    prec.assign(m_number_of_nodes + 1, -1);

    //rezervam loc pentru fiecare nod al grafului in vectorul low_link_values, in care pe fiecare pozitie i avem nivelul cel mai de sus la care putem ajunge
    //din nodul i
    low_link_values.resize(m_number_of_nodes + 1);

    //initializam vectorul cu timpiii de ajungere pentru fiecare nod in parte cu 0
    arrival_times.resize(m_number_of_nodes + 1);

    //parcurgem nodurile grafului si, pentru fiecare nod nevizitat, facem DFS
    for(int i = 0; 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 folosit in gasirea 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_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;
                    //formam componenta biconexa in aux
                    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];
                }
            }
        }
    }
}

//DFS-ul folosit pentru 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_adjancency_list[current_node].size(); i++){

        int neighbor = m_adjancency_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 Undirected_graph_coupler: Undirected_graph{
private:
    int m_number_of_left_nodes;

public:
    //CONSTRUCTORI

    //constructor cu 3 parametri: numarul de noduri, listele de adiacenta, si numarul de noduri din multimea din stanga
    Undirected_graph_coupler(int number_of_nodes, const vector<vector<int>> &adjacency_list, int number_of_left_nodes);

    //constructor fara parametri
    Undirected_graph_coupler();

    //ALGORITMI

    //citirea grafului
    void read_graph(char *file);

    //returnarea cuplajului maxim
    vector< pair<int, int> > hopcroft_karp();

private:
    //DFS-ul folosit la aflarea cuplajului maxim
    bool DFSCoupler(int node, vector<int>& left_pair, vector<int>& right_pair, vector<int>& visited);
};

//METODE PUBLICE GRAF NEORIENTAT BIPARTIT

//CONSTRUCTORI

//constructor cu 3 parametri: numarul de noduri, listele de adiacenta, numarul de noduri din multimea din stanga
Undirected_graph_coupler::Undirected_graph_coupler(int number_of_nodes, const vector<vector<int>> &adjacency_list,
                                                   int number_of_left_nodes) : Undirected_graph(number_of_nodes, adjacency_list),
                                                                               m_number_of_left_nodes(number_of_left_nodes) {}

//constructor fara parametri
Undirected_graph_coupler::Undirected_graph_coupler() {
    m_number_of_left_nodes = 0;
    m_number_of_nodes = 0;
    m_adjancency_list.resize(m_number_of_left_nodes);
}

//ALGORITMI

//citirea grafului
void Undirected_graph_coupler::read_graph(char *file) {

    ifstream f(file);
    int number_of_right_nodes, number_of_edges;

    //citim numarul de noduri din stanga si din dreapta
    f >> m_number_of_left_nodes >> number_of_right_nodes;

    //numarul de noduri ale grafului va fi suma
    m_number_of_nodes = m_number_of_left_nodes + number_of_right_nodes;

    //citim numarul de muchii
    f >> number_of_edges;

    //initializam matricea de vecini cu numaruk de noduri din stanga ale grafului nostru, deoarece matricea va retine vecinii din dreapta ai nodurilor din stanga

    m_adjancency_list.assign(m_number_of_left_nodes + 1, vector<int>());

    //citim muchie cu muchie si o pe fiecare adaugam in matricea de vecini
    for(int i = 0; i < number_of_edges; i++){
        int x, y;

        f >> x >> y;

        m_adjancency_list[x].push_back(y);
    }
}

//algoritmul hopcroft_karp() -> returneaza un vector in care pe fiecare pozitie se afla cate o muchie din cuplajul maxim al grafului
vector< pair<int,int> > Undirected_graph_coupler::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->DFSCoupler(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 GRAF NEORIENTAT BIPARTIT

//DFS-ul folosit la calcularea cuplajului maxim -> returneaza true daca reusesc sa formez un lant din nodul dat in dreapta
bool Undirected_graph_coupler::DFSCoupler(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_adjancency_list[node].size(); i++){
        int neighbor;

        //luam vecinul
        neighbor = m_adjancency_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_adjancency_list[node].size(); i++){
        int neighbor;

        //luam vecinul
        neighbor = m_adjancency_list[node][i];

        //verificam daca vecinul face parte dintr-un lant
        if(DFSCoupler(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 ORIENTED GRAPH

class Oriented_graph: protected Graph{
protected:
    vector< vector<int> > m_adjancency_list;

public:
    //CONSTRUCTORI

    //constructor cu 2 parametri: numarul de noduri si listele de adiacenta
    Oriented_graph(int number_of_nodes, const vector<vector<int>> &adjacency_list);

    //constructor fara parametri
    Oriented_graph();

    //ALGORITMI

    //citirea grafului
    void read_graph(char *file);

    //citirea grafului cu un nod sursa -> imi returneaza nodul sursa
    int read_graph_with_starting_node(char *file);

    //parcurgerea BFS(int nod) -> returneaza un vector in care pe fiecare pozitie i se afla numarul minim de arce ce trebuie parcurse pentru a ajunge
    //din nodul sursa dat in nodul i
    vector<int> BFS(int source);

    //returnarea unui vector de componente tare conexe
    vector<vector<int>> create_strongly_connected_components();

    //tarjan cu argumente
    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);

    //sortarea topoligca -> returneaza o stiva in care avem nodurile puse in ordinea data de sortarea topologica
    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 ORIENTED GRAPHS

//CONSTRUCTORI

//constructorul cu 2 parametri: numarul de noduri si listele de adiacenta
Oriented_graph::Oriented_graph(int number_of_nodes, const vector<vector<int>> &adjacency_list) : Graph(number_of_nodes),
                                                                                                 m_adjancency_list(adjacency_list) {}

//constructorul fara marametri
Oriented_graph::Oriented_graph() {
    m_number_of_nodes = 0;
    m_adjancency_list.resize(m_number_of_nodes);
}

//ALGORITMI

//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 node 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 distances 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 node] = 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
    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;
}

//metoda create_strongly_connected_components() returneaza un vector in care pe fiecare pozitie se afla o componenta tare conexa
vector< vector<int> >Oriented_graph::create_strongly_connected_components() {

    vector<vector<int>> strongly_connected_components;

    stack<int> current_component;
    int current_arrival_time = 0;

    vector<int> is_in_stack;
    is_in_stack.assign(this->m_number_of_nodes + 1, 0);

    vector<int> arrival_values;
    arrival_values.assign(this->m_number_of_nodes + 1, -1);

    vector<int> low_link_values;
    low_link_values.resize(this->m_number_of_nodes + 1);

    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
void Oriented_graph::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) {

    //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_adjancency_list[node].size(); i++){
        int neighbor = this->m_adjancency_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 -> returneaza o stiva in care sunt asezate nodurile in ordinea dara de sortarea topologica
stack<int> Oriented_graph::topological_sort() {
    vector<int> visited;
    stack<int> sort;

    visited.assign(m_number_of_nodes + 1, 0);

    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 folosit in sortarea topologica
void Oriented_graph::DFS_topological_sort(int node, stack<int> &sort, vector<int>& visited) {

    visited[node] = 1;

    for(int i = 0; i < this->m_adjancency_list[node].size(); i++){

        int neighbor = this->m_adjancency_list[node][i];

        if(visited[neighbor] == 0){

            DFS_topological_sort(neighbor, sort, visited);
        }
    }
    sort.push(node);
}


//CLASA UNORIENTED GRAPH WITH COSTS

class Unoriented_graph_with_costs:Graph{
private:
    vector< vector< pair <int,int> > > m_adjancency_list;
public:
    //CONSTRUCTORI

    //constructor cu 2 parametri: numarul de noduri si listele de adiacenta
    Unoriented_graph_with_costs(int number_of_nodes, const vector<vector<pair<int, int>>> &adjacency_list);

    //constructor fara parametri
    Unoriented_graph_with_costs();

    //ALGORITMI

    //citirea grafului sub forma listei de vecini
    void read_graph(char *file);

    //algoritmul lui prim->returneaza arborele partial de cost minim si, prin parametrul dat ca referinta, returneaza si costul
    vector< pair<int,int> > prim(int source, 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 UNORIENTED GRAPHS WITH COSTS

//CONSTRUCTORI

//constructor cu 2 parametri: numarul de noduri si listele de adiacenta
Unoriented_graph_with_costs::Unoriented_graph_with_costs(int number_of_nodes,
                                                         const vector<vector<pair<int, int>>> &adjacency_list) : Graph(number_of_nodes),
                                                                                                                 m_adjancency_list(adjacency_list) {}

//constructor fara parametri
Unoriented_graph_with_costs::Unoriented_graph_with_costs() {
    m_number_of_nodes = 0;
    m_adjancency_list.resize(0);
}

//ALGORIMTI

//citirea grafului
void Unoriented_graph_with_costs::read_graph(char *file) {

    fstream f(file);
    vector< pair <int, int> > aux;
    int number_of_edges;

    //citim numarul de noduri

    f>>this->m_number_of_nodes;

    //initializam matricea de vecini pentru numarul de noduri dat

    this->m_adjancency_list.assign(this->m_number_of_nodes + 1, aux);

    //citim numarul de muchii si apoi fiecare muchie, si pentru fiecare node ii adaugam vecinul in vectorul de vecini corespunzator in matricea de vecini

    f >> number_of_edges;

    for(int i = 0; i < number_of_edges; i++){
        int x,y,cost;

        f >> x >> y >> cost;

        m_adjancency_list[x].push_back(make_pair(y, cost));
        m_adjancency_list[y].push_back(make_pair(x, cost));
    }

}

//algoritmul lui Prim -> returneaza un vector APM si, prin parametrul dat ca referinta, costul total al APM-ului
vector< pair<int,int> >Unoriented_graph_with_costs::prim(int source, 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[source] = 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);
    }

    for(int i = 1; i < this->m_number_of_nodes; i++){
        //extragem nodul cu distanta minima <=> extragem radacina heap-ului
        int root;

        root = extract_root_min_heap(heap, positions, distances);

        //introducem nodul cu distanta minima in APM
        introduce_in_APM(root, distances, vec);

        //actualizam costul APM-ului
        cost_APM = cost_APM + distances[root];

        //introducem muchia noua de la radacina la vecin in APM-ul nostru
        APM_edges.push_back(make_pair(root, vec[root]));

        //parcurgem vecinii radacinii si eliminam vecinii care sunt deja in heap
        for(int j = 0; j < this->m_adjancency_list[root].size(); j++){
            int nod;
            nod = this->m_adjancency_list[root][j].first;
            if(positions[nod]) pop(positions[nod], heap, positions, distances);
        }
    }

    return APM_edges;
}

//METODE PRIVATE UNORIENTED GRAPH WITH COSTS

//introducerea unui nod in APM
void Unoriented_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_adjancency_list[node].size(); i++){

        int neighbor, cost;

        neighbor = this->m_adjancency_list[node][i].first;
        cost = this->m_adjancency_list[node][i].second;

        //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
void Unoriented_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);
}

//urcarea nodului in heap acolo unde ii este pozitia corecta cand facem inserarea nodului in heap
void Unoriented_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 heap-ului
int Unoriented_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;
}

//repararea heap-ului cand extragem radacina
void Unoriented_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 ORIENTED GRAPH WITH COSTS

class Oriented_graph_with_costs:Graph{
private:
    //listele de adiacenta in forma de perechi de (vecin, cost)
    vector< vector< pair<int,int> > > m_adjacency_list;

    //listele de adiacenta doar cu vecinii
    vector< vector<int> > m_neighbors;

    //matricea de costuri
    vector< vector<int> > m_costs_matrix;
public:
    //CONSTRUCTORI

    //constructor cu 2 parametri: numarul de noduri si matricea de adiacenta in format de perechi (vecin, cost)
    Oriented_graph_with_costs(int number_of_nodes, const vector<vector<pair<int, int>>> &adjacency_list);

    //constructor cu 3 parametri: numarul de noduri, listele de vecini si matricea de costuri
    Oriented_graph_with_costs(int number_of_nodes, const vector<vector<int>> &adjacency_list, const vector<vector<int>> &costs_matrix);

    //constructor fara parametri
    Oriented_graph_with_costs();

    //ALGORITMI

    //citirea grafului
    void read_graph(char *file);

    //citirea grafului cu matricea de costuri
    void read_graph_with_costs_matrix(char *file);

    //citirea matricei de costuri a grafului
    void read_costs_matrix(char *file);

    //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 -> primeste matricea de costuri si returneaza matricea de drumuri
    vector< vector<int> > bellman_ford(vector< vector<int> > costs_matrix);

    //metoda bellman-ford fara argument -> returneaza matricea drumurilor pentru graful nostru
    vector< vector<int> > bellman_ford();

    //metoda hamilton -> returneaza costul ciclului hamiltonian de cost minim; daca graful nu este hamiltonian, returneaza -1
    int hamilton();
};

//METODE PUBLICE GRAFURI ORIENTATE CU COSTURI

//CONSTRUCTORI

//constructor cu 2 parametri: numarul de noduri si listele de adiacenta in forma de perechi (vecin, cost)
Oriented_graph_with_costs::Oriented_graph_with_costs(int number_of_nodes, const vector<vector<pair<int, int>>> &adjacency_list) : Graph(number_of_nodes),
                                                                                                                                  m_adjacency_list(adjacency_list) {}

//constructor cu 3 parametri: numarul de noduri, listele de vecini si matricea de costuri

Oriented_graph_with_costs::Oriented_graph_with_costs(int number_of_nodes, const vector<vector<int>> &adjacency_list, const vector<vector<int>> &costs_matrix) :
        Graph(number_of_nodes), m_neighbors(adjacency_list), m_costs_matrix(costs_matrix) {}


//constructor fara parametri
Oriented_graph_with_costs::Oriented_graph_with_costs() {
    m_number_of_nodes = 0;
}

//ALGORITMI

//citirea grafuluica ca liste de adiacenta sub forma (vecin, cost)
void Oriented_graph_with_costs::read_graph(char *file) {
    fstream f(file);
    vector< pair<int,int> > aux;
    int number_of_edges;

    //citim numarul de noduri si initializam lista de vecini cu numarul de noduri

    f>>m_number_of_nodes;

    m_adjacency_list.assign(m_number_of_nodes + 1, aux);

    //citim numarul de muchii si apoi fiecare muchie, adaugand vecinul fiecarui node in vectorul lui de vecini din matricea de  vecini

    f >> number_of_edges;

    for(int i = 0; i < number_of_edges; i++){
        int x,y,cost;

        f >> x >> y >> cost;

        this->m_adjacency_list[x].push_back(make_pair(y,cost));
    }
}

//citirea matricii de costuri a unui graf
void Oriented_graph_with_costs::read_costs_matrix(char *file) {

    ifstream f(file);
    vector<int> aux;

    //citim numarul de noduri si initializam matricea de costuri cu numarul de noduri dat

    f >> this->m_number_of_nodes;

    m_costs_matrix.push_back(aux);

    //formam matricea de costuri

    for(int i = 1; i <= this->m_number_of_nodes; i++){

        //citim linia corespunzatoare nodului curent i in matricea de costuri

        vector<int> linie;
        //punem pe pozitia 0 valoarea 0 pentru ca noi lucram cu matricea de costuri incepand de pe pozitia 1
        linie.push_back(0);

        //citim fiecare valoare care este costul de a ajunge de la nodul i la nodul j si o punem pe pozitia linie[j]

        for(int j = 1; j <= this->m_number_of_nodes; j++){
            int val;
            f >> val;
            linie.push_back(val);
        }

        //adaugam linia nodului i in matrice

        m_costs_matrix.push_back(linie);
    }
}

//citirea grafului ca matrici separate de vecini si de costuri
void Oriented_graph_with_costs::read_graph_with_costs_matrix(char *file) {

    ifstream f(file);

    vector<int> aux;

    int number_of_edges;

    //citim numarul de noduri si numarul de muchii
    f >> m_number_of_nodes >> number_of_edges;

    //initializam matricea de costuri si matricea de adiacenta

    m_neighbors.assign(m_number_of_nodes + 1, aux);

    aux.assign(m_number_of_nodes + 1, 100000000);
    m_costs_matrix.assign(m_number_of_nodes + 1, aux);


    //citim fiecare muchie si costul acesteia si o introducem in graf
    for(int i = 0; i < number_of_edges; i++){

        int x, y, c;

        f >> x >> y >> c;
        m_neighbors[y].push_back(x);
        m_costs_matrix[x][y] = c;
    }
}

//getter pentru matricea de costuri
vector< vector<int> > Oriented_graph_with_costs::get_costs_matrix() {
    return this->m_costs_matrix;
}

//dijkstra -> returneaza vectorul cu drumuri minime pentru fiecare pozitie i de la nodul sursa dat la nodul i
vector<int> Oriented_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].first;
            cost_neighbor = this->m_adjacency_list[nod][i].second;

            //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 argument -> returneaza matricea de drumuri a grafului
vector< vector<int> > Oriented_graph_with_costs::bellman_ford() {

    //daca graful nu are setata matricea de costuri, o setam
    if(m_costs_matrix.empty()){
        vector<int> aux;
        aux.assign(m_number_of_nodes + 1, 0);
        m_costs_matrix.assign(m_number_of_nodes + 1, aux);

        for(int i = 0; i < m_adjacency_list.size(); i++){
            for(int j = 0; j < m_adjacency_list[i].size(); j++){
                m_costs_matrix[i][j] = m_adjacency_list[i][j].second;
            }
        }
    }

    return this->bellman_ford(m_costs_matrix);
}

//bellman ford cu argument -> ia matricea de costuri data si returneaza matricea de drumuri asociata
vector< vector<int> > Oriented_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] = 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;
}

//hamilton() -> returneaza costul ciclului hamiltonian minim
int Oriented_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 nodu; 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_neighbors[j].size(); k++){

                    if( i & (1 << m_neighbors[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_neighbors[j][k] ] + m_costs_matrix[ m_neighbors[j][k] ][j]);
                    }
                }
            }
        }
    }

    //aflam costul minim al unnui ciclu
    int mini = 100000000;

    for(int i = 0; i < m_neighbors[0].size(); i++){
        mini = min(mini, minimum_costs[ (1 << m_number_of_nodes) - 1 ][ m_neighbors[0][i] ] + m_costs_matrix[ m_neighbors[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:Graph{
private:
    vector< vector<int> > m_adjacency_list;
    vector<int> m_fathers_array;
    vector<int> m_ranks_array;
public:
    //CONSTRUCTORI

    //constructor cu 1 parametru: numarul de noduri
    Tree(int number_of_nodes);

    //constructor cu 2 parametri: numarul de noduri si listele de adiacenta
    Tree(int number_of_nodes, const vector<vector<int>> &adjacency_list);

    //constructor fara parametri
    Tree();
    //citirea arborelui
    void read_graph(char *file);

    //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);

    //setarea numarului 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 ARBORE

//CONSTRUCTORI

//constructor cu 1 parametru: numarul de noduri
Tree::Tree(int number_of_nodes){
    m_number_of_nodes = number_of_nodes;
    vector<int> aux;
    aux.assign(m_number_of_nodes + 1, 0);
    m_adjacency_list.assign(m_number_of_nodes + 1, aux);

    m_fathers_array.push_back(0);
    for(int i = 1; i <= m_number_of_nodes; i++){
        m_fathers_array.push_back(i);
    }

    m_ranks_array.assign(m_number_of_nodes + 1, 1);
}

//constructor cu 2 parametri: numarul de noduri si listele de adiacenta

Tree::Tree(int number_of_nodes, const vector<vector<int>> &adjacency_list) : Graph(number_of_nodes), m_adjacency_list(adjacency_list) {}

//constructor fara parametri
Tree::Tree() {
    m_number_of_nodes = 0;
    m_adjacency_list.resize(m_number_of_nodes);
}

//ALGORITMI

//citirea arborelui
void Tree::read_graph(char *file) {

    ifstream f(file);
    vector<int> aux;

    //citim numarul de noduri si initializam lista de vecini cu cu numarul de noduri dat

    f >> this->m_number_of_nodes;

    this->m_adjacency_list.assign(this->m_number_of_nodes + 1, aux);

    //citim muchiile arborelui si marcam pentru fiecare node vecinul sau in matricea de vecini

    for(int i = 0; i < this->m_number_of_nodes; i++){
        int x, y;
        f >> x >> y;

        this->m_adjacency_list[x].push_back(y);
        this->m_adjacency_list[y].push_back(x);
    }
}

//parcurgerea cu BFS pentru diametru
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();
    }
}
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);
}

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;
}

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:Oriented_graph{
private:
    vector< vector<int> > m_capacities_matrix;

public:
    //CONSTRUCTORI

    //constructor cu 3 parametri: numarul de noduri, listele de adiacenta si matricea de capacitati
    Flow_network(int number_of_nodes, const vector<vector<int>> &adjancency_list,
                 const vector<vector<int>> &capacities_matrix);

    //constructor fara parametri
    Flow_network();

    //ALGORITMI

    //citirea fluxului de transport
    void read_graph(char *file);

    //metoda edmonds_karp -> returneaza fluxul maxim care poate fi transportat
    int edmonds_karp();

private:
    //BFS-ul folosit in aflarea fluxului maxim
    int BFS(vector<int>& father, vector< vector<int> >& f, vector<int>& visited);
};

//METODE PUBLICE RETEA DE TRANSPORT

//CONSTRUCTORI

//constructor cu 3 parametri: numarul de noduri, listele de adiacenta si matricea de capacitati
Flow_network::Flow_network(int number_of_nodes, const vector<vector<int>> &adjancency_list, const vector<vector<int>> &capacities_matrix) :
        Oriented_graph(number_of_nodes, adjancency_list), m_capacities_matrix(capacities_matrix) {}

//constructor fara parametri
Flow_network::Flow_network() {
    m_number_of_nodes = 0;
    m_capacities_matrix.resize(0);
    m_adjancency_list.resize(0);
}

//ALGORITMI

//citirea retelei de transporturi
void Flow_network::read_graph(char *file) {
    ifstream f(file);
    vector<int> aux;
    int number_of_edges;

    //citim numarul de noduri si numarul de muchii si initializam lista de vecini si matricea de capacitati

    f >> m_number_of_nodes >> number_of_edges;

    m_adjancency_list.assign(m_number_of_nodes + 1, aux);
    aux.assign(m_number_of_nodes + 1, 0);
    m_capacities_matrix.assign(m_number_of_nodes + 1, aux);

    //parcurgem muchiile si, la fiecare, adaugam vecinii fiecarui nod in listele de vecini si actualizam capacitatea de pe pozitia corespunzatoare muchiei in matricea de capacitati
    for(int i = 0; i < number_of_edges; i++){
        int x, y, capacity;

        f >> x >> y >> capacity;

        m_capacities_matrix[x][y] = m_capacities_matrix[x][y] + capacity;

        m_adjancency_list[x].push_back(y);
        m_adjancency_list[y].push_back(x);
    }

}

//edmonds_karp() -> returneaza fluxul maxim
int Flow_network::edmonds_karp() {

    //initializam flow-ul maxim cu 0
    int flow = 0;

    //initializam vectorul de tati si matricea cu fluxuri
    vector<int> father;
    vector< vector<int> > f;
    vector<int> visited;
    vector<int> aux;

    aux.assign(m_number_of_nodes + 1, 0);

    father.assign(m_number_of_nodes + 1, 0);
    f.assign(m_number_of_nodes + 1, aux);

    while(BFS(father,f,visited)){
        for(int i = 0; i < m_adjancency_list[m_number_of_nodes].size(); i++){
            int node;

            node = m_adjancency_list[m_number_of_nodes][i];

            if(f[node][m_number_of_nodes] != m_capacities_matrix[node][m_number_of_nodes] && visited[node] != 0) {

                father[m_number_of_nodes] = node;

                int fmin = 1000000;

                for (node = m_number_of_nodes; node != 1; node = father[node]) {
                    fmin = min(fmin, m_capacities_matrix[father[node]][node] - f[father[node]][node]);
                }

                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;
                    }

                    flow = flow + fmin;
                }
            }
        }
    }
    return flow;
}

//METODE PRIVATE RETEA DE TRANSPORT

//BFS-ul folosit in edmonds_karp() in 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
    cd.assign(1024,0);

    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;

    for(int i = 1; i <= cd[0]; i++){
        int node;

        node = cd[i];

        if(node != m_number_of_nodes) {

            for (int j = 0; j < m_adjancency_list[node].size(); j++) {
                int neighbor;

                neighbor = m_adjancency_list[node][j];

                if (m_capacities_matrix[node][neighbor] != f[node][neighbor] && visited[neighbor] == 0) {

                    visited[neighbor] = 1;

                    cd[++cd[0]] = neighbor;

                    father[neighbor] = node;
                }
            }
        }
    }

    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 parametri: numarul de nodrui, matricea de muchii si vectorul avand pe fiecare pozitie i perechi de forma (x,y), insemnand ca muchia
    //numarul i este de la x la y
    Multigraph(int number_of_nodes, const vector<vector<int>> &nodes_edges, const vector<pair<int, int>> &edges);

    //constructor fara parametri
    Multigraph();

    //ALGORITMI

    //citirea multigrafului
    void read_graph(char *file);

    //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:
    bool check_even_degrees();
};

//METODE PUBLICE MULTIGRAF

//CONSTRUCTORI

//constructor cu 3 parametri: numarul de nodrui, matricea de muchii si vectorul avand pe fiecare pozitie i perechi de forma (x,y), insemnand ca muchia
//numarul i este de la x la y
Multigraph::Multigraph(int number_of_nodes, const vector<vector<int>> &nodes_edges, const vector<pair<int, int>> &edges)
        : Graph(number_of_nodes), m_nodes_edges(nodes_edges), m_edges(edges) {}

//constructor fara parametri
Multigraph::Multigraph() {
    m_number_of_nodes = 0;
    m_nodes_edges.resize(0);
    m_edges.resize(0);
}

//ALGORITMI

//citirea multigrafului
void Multigraph::read_graph(char *file) {
    ifstream f(file);

    int number_of_edges;

    vector<int> aux;

    //citim numarul de noduri si numarul de muchii

    f >> m_number_of_nodes >> number_of_edges;

    //initializam matricea de muchii si vectorii cu nodurile sursa si nodurile destinatie ale muchiilor

    m_nodes_edges.assign(m_number_of_nodes + 1, aux);
    m_edges.resize(number_of_edges + 1);

    for(int i = 0; i < number_of_edges; i++){

        //citim fiecare muchie in parte

        int x,y;
        f >> x >> y;

        //actualizam matricea de muchii: la x si la y marcam existenta muchiei i

        m_nodes_edges[x].push_back(i);
        m_nodes_edges[y].push_back(i);

        //marcam cum exact este aceasta muchie: de la x la y, deci actualizam vectorul de noduri de sursa ( adaugand x)
        // si cel de noduri destinatie (adaugand y)

        m_edges[i] = make_pair(x,y);
    }

}

//euler() -> returneaza un vector continand ciclul minim eulerian din graf pornind de la nodul dat sau doar valoarea -1 daca graful nu este eulerian
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;

}

//HELPERE

//AFISARI DE VECTORI

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 <<" ";
    }
}

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";
    }
}

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";
    }
}

void print_stack(stack<int> s, char *file){
    ofstream g(file);

    while(!s.empty()){

        g << s.top() << " ";
        s.pop();
    }
}

//CITIRI DE VECTORI

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);
    }
}

//PROBLEME DE PE INFOARENA

void solve_infoarena_bfs(){

    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");
}

void solve_infoarena_dfs(){
    Undirected_graph g;
    ofstream out("../dfs.out");
    int number;

    g.read_graph("../dfs.in");
    number = g.number_of_connected_components();

    out << number;
}

void solve_infoarena_biconex(){
    Undirected_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");
}

void solve_infoarena_ctc(){
    Oriented_graph g;
    vector< vector<int> > strongly_connected_components;

    g.read_graph("../ctc.in");

    strongly_connected_components = g.create_strongly_connected_components();

    print_vector_of_vectors(strongly_connected_components, "../ctc.out");
}

void solve_infoarena_sortaret(){
    Oriented_graph g;
    stack<int> topological_sort;

    g.read_graph("../sortaret.in");

    topological_sort = g.topological_sort();

    print_stack(topological_sort, "../sortaret.out");
}

void solve_havel_hakimi(){
    Graph g;
    vector<int> v;
    ofstream out("../hakimi.out");

    read_vector(v,"../hakimi.in");

    if(g.hakimi(v) == true)  out << "Posibil";
    else out << "Imposibil";
}

void solve_infoarena_apm(){
    Unoriented_graph_with_costs g;
    vector< pair<int,int> > apm;
    ofstream out("../apm.out");
    int cost_APM = 0;

    g.read_graph("../apm.in");
    apm = g.prim(1,cost_APM);

    out << cost_APM << "\n";

    out << apm.size() << "\n";

    for(int i = 0; i < apm.size(); i++){
        out << apm[i].first << " " << apm[i].second << "\n";
    }
}

void solve_infoarena_dijkstra(){
    Oriented_graph_with_costs g;
    vector<int> minimum_distances;

    g.read_graph("../dijkstra.in");
    minimum_distances = g.dijkstra(1);

    print_vector(minimum_distances, "../dijkstra.out", 1);
}

void solve_infoarena_royfloyd(){
    Oriented_graph_with_costs g;
    vector< vector<int> > paths;

    g.read_costs_matrix("../royfloyd.in");
    paths = g.bellman_ford(g.get_costs_matrix());

    print_vector_of_vectors(paths,"../royfloyd.out",1,false);
}

void solve_infoarena_maxflow(){
    Flow_network f;
    ofstream out("../maxflow.out");
    int maxflow;

    f.read_graph("../maxflow.in");

    maxflow = f.edmonds_karp();

    out << maxflow;
}

void solve_infoarena_darb(){
    ofstream out("../darb.out");
    Tree t;
    t.read_graph("../darb.in");


    int diameter = 0, last = 0;

    t.BFS(1, diameter, last);
    t.BFS(last,diameter,last);

    out << diameter;
}

void solve_infoarena_ciclueulerian(){
    Multigraph g;
    vector<int> euler_cycle;

    g.read_graph("../ciclueuler.in");

    euler_cycle = g.euler(1);

    //dam ca argument la printarea vectorului -1 pentru ca printarea sa inceapa de pe pozitia 0

    print_vector(euler_cycle, "../ciclueuler.out", -1);
}

void solve_infoarena_hamilton(){
    ofstream out("../hamilton.out");

    Oriented_graph_with_costs g;
    int hamilton;

    g.read_graph_with_costs_matrix("../hamilton.in");
    hamilton = g.hamilton();

    if(hamilton == -1) out << "Nu exista solutie";
    else out << hamilton;
}

void solve_infoarena_cuplajmaxim(){
    Undirected_graph_coupler g;
    ofstream out("../cuplaj.out");

    g.read_graph("../cuplaj.in");

    vector< pair<int, int> > maximum_coupler;

    maximum_coupler = g.hopcroft_karp();

    out << maximum_coupler.size() << "\n";

    for(int i = 0; i < maximum_coupler.size(); i++){
        out << maximum_coupler[i].first << " " << maximum_coupler[i].second << "\n";
    }
}

void solve_infoarena_paduridisjuncte(){
    ifstream in("../disjoint.in");
    ofstream out("../disjoint.out");
    int nodes, number_of_tasks;
    Tree set;

    //citim numarul de multimi
    in >> nodes;

    //numarul de multimi <=> numarul de noduri ale arborelui (initial fiecare multime are doar elementul i), asa ca setam ca arborele cu numar de noduri = numar de multimi

    set.set_number_of_nodes(nodes);

    //initial, tatal fiecarui nod este chiar el (pentru ca fiecare multime i contine doar elementul i) si rangul fiecarui arbore este 1
    set.initialize_fathers_array();
    set.initialize_ranks_array(1);

    //citim numarul de operatii
    in >> number_of_tasks;

    //citim fiecare operatie
    for(int i = 0; i < number_of_tasks; i++){

        int task, x, y;
        in >> task >> x >> y;

        if(task == 2){
            //daca task-ul este 2, atunci trebuie sa verificam daca x si y se afla in aceeasi multime; afisam DA / NU, dupa caz

            if( set.find(x) == set.find(y) ) out << "DA\n";
            else out << "NU\n";

        }else{
            //daca task-ul este 1, atunci trebuie sa reunim multimea in care se afla elementul x cu cea in care se afla elementul y;
            int index_x, index_y;

            index_x = set.find(x);
            index_y = set.find(y);

            set.unify(index_x, index_y);

        }
    }
}

//PROBLEMA LEETCODE

/*
class Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        Undirected_graph g;
        g.set_number_of_nodes(n);
        g.set_adjacency_list(connections);
        vector<vector<int>> result;
        result = g.find_critical_edges();
        return result;
    }
};
 */

//PROBLEMELE INFOARENA
int main() {
    //BFS INFOARENA

    //solve_infoarena_bfs();

    //DFS INFOARENA
    //solve_infoarena_dfs();

    //COMPONENTE BICONEXE INFOARENA

    //solve_infoarena_biconex();

    //CTC INFOARENA

    //solve_infoarena_ctc();

    //SORTARE TOPOLOGICA INFOARENA

    //solve_infoarena_sortaret();

    //HAVEL HAKIMI

    //solve_havel_hakimi();

    //APM INFOARENA - ALGORITMUL LUI PRIM

    solve_infoarena_apm();

    //PADURI DE MULTIMI DISJUNCTE INFOARENA

    //Cele 2 multimi vor fi reprezentate ca 1 arbore

    //solve_infoarena_paduridisjuncte();

    //DIJKSTRA INFOARENA

    //solve_infoarena_dijkstra();

    //BELLMAN FORD

    //solve_infoarena_royfloyd();

    //FLUXUL MAXIM INFOARENA

    //solve_infoarena_maxflow();

    //DIAMETRUL UNUI ARBORE

    //solve_infoarena_darb();

    //CICLUL EULERIAN INFOARENA

    //solve_infoarena_ciclueulerian();

    //CICLUL HAMILTONIAN DE COST MINIM INFOARENA

    //solve_infoarena_hamilton();

    //CUPLAJ MAXIM IN GRAF BIPARTIT INFOARENA

    //solve_infoarena_cuplajmaxim();

    return 0;
}