Cod sursa(job #2818357)

Utilizator MihaelaDanilaDanila Mihaela MihaelaDanila Data 15 decembrie 2021 22:08:02
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 11.46 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <stack>

using namespace std;

//CLASA GRAPH DE BAZA

class Graph{

//DATELE MEMBRE

protected:
    int m_number_of_nodes;
    //numarul de noduri


//METODELE

public:

    //functia de citire virtuala -> implementata diferit in fiecare dintre clase
    virtual void read_graph(char *file);
    //parcurgerea in latime
    virtual vector<int> BFS(int node);
    //parcurgerea in adancime
    virtual void DFS(int node, vector<int>& visited);
};

//METODE PUBLICE

void Graph::read_graph(char *file) {
    return;
}

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

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

//CLASA UNORIENTED GRAPH

class Unoriented_graph:Graph{
protected:
    vector< vector<int> > m_adjancency_list;
public:
    //citirea grafului
    void read_graph(char *file);
    //parcurgerea in adancime DFS
    void DFS(int node, vector<int>& visited);
    //numararea componentelor conexe
    int number_of_connected_components();
    //returnarea unui vector cu componentele conexe
    vector< unordered_set<int> > generate_biconnected_components();

private:
    void DFSBiconnected(int current_node, int prec, int step, vector<int>& arrival_values, vector<int>& low_link_values,vector<unordered_set<int>>& biconnected_components,stack<pair <int, int>>& current_biconnected_components);
};

//METODE PUBLICE GRAFURI NEORIENTATE

void Unoriented_graph::read_graph(char *file) {
    ifstream f(file);

    vector<int> aux;
    int number_edges;

    //citim numarul de noduri si numarul de muchii
    f>>this->m_number_of_nodes >> number_edges;

    //rezervam in matricea de vecini spatiu pentru numarul de noduri ale grafului
    this->m_adjancency_list.assign(this->m_number_of_nodes + 1, aux);

    //citim fiecare muchie si o marcam pentru ambele capete

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

        f >> x >> y;

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

void Unoriented_graph::DFS(int node, vector<int> &visited) {

    //marcam nodul curent ca vizitat

    visited[node] = 1;

    //parcurgem vecinii si pentru fiecare vecin nevizitat aplicam recursiv DFS
    for(int i = 0; i < this->m_adjancency_list[node].size(); i++){

        if(visited[ this->m_adjancency_list[node][i] ] == 0){
            DFS( this->m_adjancency_list[node][i], visited);
        }
    }
}

int Unoriented_graph::number_of_connected_components() {

    //numarul componentelor conexe il vom tine in nr
    int number = 0;

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

    //pentru fiecare nod nevizitat parcurgem din copil in copil prin DFS; de fiecare data cand dam de un nod nevizitat inseamna ca avem o noua componenta conexa
    for(int node = 1; node <= this->m_number_of_nodes; node++){
        if(visited[node] == 0){
            number++;
            DFS(node, visited);
        }
    }

    return number;
}

vector< unordered_set<int> >Unoriented_graph::generate_biconnected_components(){

    vector<unordered_set<int>> biconnected_components;
    stack<pair <int, int>> current_biconnected_component;

    vector<int> arrival_value;
    vector<int> low_link_values;

    //initializam timpii de sosire si nivelul cel mai de sus pentru fiecare nod

    arrival_value.assign(this->m_number_of_nodes + 1, -1);
    low_link_values.resize(this->m_number_of_nodes + 1);

    //facem DFS

    DFSBiconnected(1,0,0,arrival_value,low_link_values,biconnected_components,current_biconnected_component);

    return biconnected_components;
}

//METODE PRIVATE GRAFURI NEORIENTATE
void Unoriented_graph::DFSBiconnected(int current_node, int prec, int step, vector<int>& arrival_values, vector<int>& low_link_values,vector<unordered_set<int>>& biconnected_components,stack<pair <int, int>>& current_biconnected_components){

    //marcam ca vizitat nodul curent
    arrival_values[current_node] = step;

    //momentan nivelul minim de intoarcere e nivelul curent, adica pasul
    low_link_values[current_node] = step;

    //parcurgem vecinii nodului curent
    for(int i = 0; i < this->m_adjancency_list[current_node].size(); i++){

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

        if(neighbor != prec){
            //verificam pe ce fel de muchie suntem
            //daca vecinul curent a mai fost vizitat inseamna ca am dat de o muchie de intoarcere, altfel suntem pe o muchie in jos

            if(arrival_values[neighbor] == -1){

                //am dat de o noua muchie din componenta biconexa curenta, asa ca o adaugam in stiva
                current_biconnected_components.push(make_pair(current_node, neighbor));

                //apelam DFS pentru vecinul curent
                DFSBiconnected(neighbor, current_node, step + 1,arrival_values,low_link_values,biconnected_components,current_biconnected_components);

                //verificam daca atunci cand ne am dus mai departe in graf
                // am dat de o muchie de intoarcere care ne duce mai sus decat ne ducea nodul acesta inainte

                if(low_link_values[current_node] > low_link_values[neighbor]){
                    low_link_values[current_node] = low_link_values[neighbor];
                }

                //verificam daca am ajuns la finalul componentei biconexe

                if(low_link_values[neighbor] >= arrival_values[current_node]){
                    //trebuie sa adaugam noua componenta biconexa in vectorul de componenete biconexe
                    //si sa golim stiva cu muchiile componentei biconexe curente
                    unordered_set<int> aux;
                    int aux1, aux2;

                    do{

                        aux1 = current_biconnected_components.top().first;
                        aux2 = current_biconnected_components.top().second;

                        aux.insert(aux1);
                        aux.insert(aux2);

                        current_biconnected_components.pop();

                    } while (aux1 != current_node || aux2 != neighbor);

                    biconnected_components.push_back(aux);
                }
            }else{
                //avem o muchie de intoarcere, trebuie sa verificam daca nu cumva duce mai sus

                if(low_link_values[current_node] > arrival_values[neighbor]){
                    low_link_values[current_node] = arrival_values[neighbor];
                }
            }
        }
    }
}

//CLASA ORIENTED GRAPH

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

public:
    void read_graph(char *file);
    int read_graph_with_starting_node(char *file);
    vector<int> BFS(int source);
};

//METODE PUBLICE ORIENTED GRAPHS

//citirea grafului orientat (fara costuri)
void Oriented_graph::read_graph(char *file) {

    ifstream f(file);

    vector<int> aux;
    int number_edges;

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

    //rezervam in matricea de vecini spatiu pentru numarul de noduri ale grafului

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

    //citim fiecare muchie si o adaugam in lista de adiacenta, prin adagarea vecinului nodului din care porneste muchia

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

        f>>x>>y;

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

//citirea grafului orientat (fara costuri) cu nod de pornire

int Oriented_graph::read_graph_with_starting_node(char *file) {

    ifstream f(file);

    vector<int> aux;
    int number_edges, source;

    //citim numarul de noduri, numarul de muchii si nodul de pornire
    f >> this->m_number_of_nodes >> number_edges >> source;

    //reyervam spatiu in matricea de vecini pentru numarul de noduri ale grafului
    this->m_adjancency_list.assign(this->m_number_of_nodes + 1, aux);

    //parcurgem fiecare muchie si o adaugam in lista de adiacenta, prin adaugarea vecinului la nodul din care porneste muchia

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

        f >> x >> y;

        this->m_adjancency_list[x].push_back(y);
    }
    return source;
}

//BFS -> returneaza un vector in care pe pozitia i se afla numarul minim de arce ce trebuie parcurse de la sursa data pana la nodul i

vector<int> Oriented_graph::BFS(int source) {
    //initializam vectorul de distante minime

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

    int curent;

    //in coada vom pune nodurile pe massura ce le parcurgem
    queue<int> current_nodes;

    //initial toate nodurile sunt nevizitate, asaa ca initializam visited[orice nod] = 0
    vector<int> visited;
    visited.assign(this->m_number_of_nodes + 1, 0);

    //adaugam nodul sursa in coada si il marcam ca si vizitat
    current_nodes.push(source);
    visited[source] = 1;

    //actualizam vectorul de distante pentru nodul curent cu distanta pana la el, adica 1
    distances[source] = distances[source] + 1;

    //facem BFS-ul
    while( !current_nodes.empty() ){

        curent = current_nodes.front();

        //parcurgem vecinii nodului curent si pe fiecare vecin nevizitat il adaugam in coada, ii actualizam distanta pana la el si il marcam ca si vizitat

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

            if(visited[ this->m_adjancency_list[curent][i] ] == 0){

                current_nodes.push(this->m_adjancency_list[curent][i] );

                distances[ current_nodes.back() ] = distances[curent] + 1;

                visited[ this->m_adjancency_list[curent][i] ] = 1;
            }
        }

        //am terminat cu nodul curent, il scoatem din coada
        current_nodes.pop();
    }

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

        distances[i]--;
    }

    return distances;
}

//CLASA UNORIENTED GRAPH WITH COSTS

class Unoriented_graph_with_costs:Unoriented_graph{
private:

};

//CLASA ORIENTED GRAPH WITH COSTS

class Oriented_graph_with_costs:Oriented_graph{
private:

};

//CLASA RETELE DE TRANSPORT

class Flow_network:Oriented_graph{
private:

};

//CLASA MULTIGRAF

class Multigraph:Graph{
private:

};

//HELPERE
void print_vector(vector<int> v, char *file){
    ofstream g(file);
    vector<int>::iterator it;

    for(it = v.begin() + 1; it != v.end(); it++){
        g << *it <<" ";
    }
}

void print_vector_of_unordered_sets(vector< unordered_set<int> > v, char *file){
    ofstream g(file);
    vector< unordered_set<int> >::iterator it;
    unordered_set<int>::iterator it_u;

    g << v.size() << "\n";

    for(it = v.begin(); it != v.end(); it++){

        for(it_u = it->begin(); it_u != it->end(); it_u++){
            g << *it_u << " ";
        }
        g << "\n";
    }
}

int main() {
            //BFS INFOARENA

    /*Oriented_graph g;
    int source;
    vector<int> distances;

    source = g.read_graph_with_starting_node("../bfs.in");

    distances = g.BFS(source);

    print_vector(distances, "../bfs.out");*/

            //DFS INFOARENA
    /*Unoriented_graph g;
    ofstream out("../dfs.out");
    int number;

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

    out << number;*/

            //COMPONENTE BICONEXE INFOARENA

    Unoriented_graph g;
    vector< unordered_set<int> > biconnected_components;

    g.read_graph("../biconex.in");
    biconnected_components = g.generate_biconnected_components();

    print_vector_of_unordered_sets(biconnected_components, "../biconex.out");
    return 0;
}