Cod sursa(job #2788583)

Utilizator HadircaDionisieHadirca Dionisie HadircaDionisie Data 25 octombrie 2021 23:43:42
Problema Componente biconexe Scor 42
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.1 kb
#include <bits/stdc++.h>

using namespace std;

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

class Graph {

private:

    //Variabile private
    static int time;

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

    //Functii private

    void BFS(int starting_vertex, int *distances);

    void DFS(int vertex,int* visited);

    void BCC(int vertex, int* timer, int* lowest_reachable, int* visited, int* isArticulationPoint, int* parent, stack<int>& vertices_stack,vector<vector<int>>& components);

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

int Graph::time = 0;

//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 BCC_Helper(int vertex,vector<vector<int>> & components, stack<int>& vertices_stack,int* isArticulationPoint){
    isArticulationPoint[vertex] = 1;
    components.push_back(vector<int>());
    int n = components.size();
    while(vertices_stack.top()!=vertex){
        components[n-1].push_back(vertices_stack.top());
        cout<<vertices_stack.top()<<' ';
        vertices_stack.pop();
    }
    components[n-1].push_back(vertices_stack.top());
    cout<<vertices_stack.top();
    cout<<"\n";
}

void Graph::BCC(int vertex, int* timer, int* lowest_reachable, int* visited, int* isArticulationPoint, int* parent, stack<int>& vertices_stack,vector<vector<int>>& components){

    int children = 0;
    vertices_stack.push(vertex);
    visited[vertex] = 1;
    timer[vertex] = time;
    lowest_reachable[vertex] = time;
    time+=1;

    for(auto neighbor : adjacency_list[vertex]){

        if(!visited[neighbor]){
            children+=1;
            parent[neighbor] = vertex;
            if(children>1){
                vertices_stack.push(vertex);
            }
            BCC(neighbor, timer, lowest_reachable, visited, isArticulationPoint, parent, vertices_stack, components);



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

            if(parent[vertex] != 0 && lowest_reachable[neighbor] >= timer[vertex])
                BCC_Helper(vertex,components,vertices_stack,isArticulationPoint);

        }

        else if (neighbor!=parent[vertex])
            lowest_reachable[vertex] = min(lowest_reachable[vertex],timer[neighbor]);
    }

    if(parent[vertex] == 0 && children > 1){
        BCC_Helper(vertex,components,vertices_stack,isArticulationPoint);
        vertices_stack.pop();
    }

}

#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() {

    int* timer = (int*)calloc(vertices+1,sizeof(int));
    int* lowest_reachable = (int*)calloc(vertices+1,sizeof(int));
    int* visited = (int*)calloc(vertices+1,sizeof(int));
    int* isArticulationPoint = (int*)calloc(vertices+1,sizeof(int));
    int* parent = (int*)calloc(vertices+1,sizeof(int));
    vector<vector<int>> components;
    stack<int> vertices_stack;

    for(int i = 1;i<vertices+1;i++){
        if(!visited[i]){
            BCC(i,timer,lowest_reachable,visited,isArticulationPoint,parent,vertices_stack,components);
        }
    }
    if(!vertices_stack.empty()){
        components.push_back(vector<int>());
        while(!vertices_stack.empty()){
            components[components.size()-1].push_back(vertices_stack.top());
            vertices_stack.pop();
        }
    }

    fout<<components.size()<<'\n';

    for(int i = 0;i<components.size();i++){
        for(int j : components[i]){
            fout<<j<<' ';
        }
        fout<<'\n';
    }
    free(timer);
    free(lowest_reachable);
    free(visited);
    free(isArticulationPoint);
    free(parent);
}

#pragma endregion