Cod sursa(job #2788758)

Utilizator HadircaDionisieHadirca Dionisie HadircaDionisie Data 26 octombrie 2021 13:48:58
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 7.43 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

struct Tracker{
    int discovery_time;
    int lowest_reachable;
    Tracker(int d = 0,int l = 0):discovery_time(d),lowest_reachable(l){ }
};

class Graph {

private:

    //Variabile private

    int vertices;
    int edges;
    bool oriented;
    vector<int> *adjacency_list;

    //To compute:
    vector<unordered_set<int>> biconnected_components;

    //Functii private

    void BFS(int starting_vertex, int *distances);

    void DFS(int vertex,int* visited);

    void BCC(int vertex,vector<int>& parent, stack<int>& vertices_stack, vector<Tracker>& tracker,int& timer);

public:

    Graph(int vertices = 0, int edges = 0, bool oriented = false);

    ~Graph();

    void infoarena_graph();

    void show_my_graph();

    void solve_distances(int starting_vertex);

    void solve_connected_components();

    void solve_biconnected();

};

int main() {
    int N,M;

    fin>>N>>M;

    Graph g(N,M, false);
    g.infoarena_graph();

    g.solve_biconnected();

}


#pragma region Initialization
Graph::Graph(int vertices, int edges, bool oriented) : vertices(vertices), edges(edges), oriented(oriented) {
    adjacency_list = new vector<int>[vertices + 1];
}

Graph::~Graph() {
    delete[] adjacency_list;
}

void Graph::infoarena_graph() {
    int x, y;
    if (oriented) {
        for (int i = 1; i <= edges; i++) {
            fin >> x >> y;
            adjacency_list[x].push_back(y);
        }
    } else {
        for (int i = 1; i <= edges; i++) {
            fin>>x>>y;
            adjacency_list[x].push_back(y);
            adjacency_list[y].push_back(x);
        }
    }
}

void Graph::show_my_graph() {
    for(int i = 1;i<vertices+1;i++){
        cout<<i<<"=>";

        for(int j : adjacency_list[i]){
            cout<<j<<' ';
        }
        cout<<'\n';
    }
}

#pragma endregion

//Algorithm implementations
#pragma region Algorithms

void Graph::BFS(int starting_vertex, int *distances) {

    int* visited = (int*) calloc(vertices+1,sizeof (int));
    queue<int> que;
    que.push(starting_vertex);

    distances[starting_vertex] = 1;
    visited[starting_vertex] = 1;

    while (!que.empty()) {
        int current_node = que.front();
        que.pop();

        for (auto neighbor : adjacency_list[current_node]) {
            if (!visited[neighbor]) {
                que.push(neighbor);
                visited[neighbor] = 1;
                distances[neighbor] = distances[current_node] + 1;
            }
        }
    }

    free(visited);
}

void Graph::DFS(int vertex, int *visited) {

    visited[vertex] = 1;

    for(auto neighbor : adjacency_list[vertex])
        if(!visited[neighbor])
            DFS(neighbor,visited);
}

void Graph::BCC(int vertex,vector<int>& parent, stack<int>& vertices_stack, vector<Tracker>& tracker,int& timer){

    // consider lowest reachable value as being a better path from a node to another
    // for example if we want to reach a certain point and we have 2 neighbors with different discovery time we will chose
    // the one with the less value because we want to reach faster that certain point

    // increment the discovery time of the vertex you are visiting
    // this is the only information you posses at the moment
    tracker[vertex].discovery_time = tracker[vertex].lowest_reachable = ++timer;

    for(int neighbor : adjacency_list[vertex]){
        //now for each neighbor you are checking in adjacency list you are pushing on stack the vertex you are currently visiting
        //assuming it is an articulation point

        vertices_stack.push(vertex);

        //if the neighbor you are checking has not been visited yet you will visit him next via DFS
        if(parent[neighbor]==-1){

            parent[neighbor] = vertex; //set the parent of neighbor to be te current node
            BCC(neighbor,parent,vertices_stack,tracker,timer); //DFS


            //After you reach a point when DFS cant visit unvisited nodes you get back and update the values of your vertex lowest_reachable point
            //with the values of the neighbor you currently visited and set it to the min value between both of them

            tracker[vertex].lowest_reachable = min(tracker[neighbor].lowest_reachable,tracker[vertex].lowest_reachable);

            //You do this operation until you are in a vertex which has its discovery time less than or equal to the lowest reachable
            //value of the neighbor you currently visited


            //if you manage to find such a vertex, that means it is an articulation point, and all the vertices
            //you pushed into the stack by now are part of a biconnected component

            if(tracker[vertex].discovery_time <= tracker[neighbor].lowest_reachable){
                int aux;
                biconnected_components.push_back(unordered_set<int>());
                int n = biconnected_components.size();
                aux = vertices_stack.top();
                while(aux!=vertex){
                    if(biconnected_components[n-1].find(aux)==biconnected_components[n-1].end()) {          //here we save the results
                        biconnected_components[n - 1].insert(aux);
                    }
                    aux = vertices_stack.top();
                    vertices_stack.pop();
                }
                biconnected_components[n-1].insert(aux);
            }
        }

        //if the neighbor you are visiting has been actually visited, we need to check if it's discovery time is less then our lowest reachable value
        //if so, that means you have a path to that node that is better than the path you are on right now, so when you
        //get back by recursion it will tell the other vertices that he found a better path and will set all other vertices' lowest_reachable value to the minimal one
        //so it will form a biconnected component
        else{
            tracker[vertex].lowest_reachable = min(tracker[neighbor].discovery_time, tracker[vertex].lowest_reachable);
        }
    }
}



#pragma endregion


//infoarena solutions
#pragma region Solutions

//Minimal distances BFS problem
void Graph::solve_distances(int starting_vertex) {
    int *distances = (int*)calloc(vertices+1,sizeof (int));

    BFS(starting_vertex,distances);

    for(int i = 1;i<vertices+1;i++)
        fout<<distances[i] - 1<<' ';

    free(distances);
}

//Connected compontents DFS problem
void Graph::solve_connected_components() {

    int counter = 0;
    int* visited = (int*)calloc(vertices+1,sizeof (int));

    for(int i = 1;i<vertices + 1;i++)
        if(!visited[i]){
            DFS(i,visited);
            counter++;
        }

    fout<<counter;
    free(visited);
}

void Graph::solve_biconnected() {

    //initialize the stuff you will work with
    stack<int> vertices_stack;
    vector<int> parent(vertices+1,-1);
    vector<Tracker> tracker(vertices+1,(0,0));
    //tracker struct that track the discovery time and lowest reachable value of a vertex



    //global timer for discovery time and lowest reachable value
    int timer = 0;

    //for each vertex if it hasn't been visited call the BCC() function
    for(int i = 1;i<vertices+1;i++){
        if(parent[i] == -1){
            parent[i] = i;
            BCC(i,parent,vertices_stack,tracker,timer);
        }
    }

    fout<<biconnected_components.size()<<'\n';
    for(auto components : biconnected_components){
        for (auto i : components)
            fout<<i<<' ';
        fout<<'\n';
    }
}

#pragma endregion