Cod sursa(job #2788997)

Utilizator HadircaDionisieHadirca Dionisie HadircaDionisie Data 26 octombrie 2021 19:14:44
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.66 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <queue>
#include <unordered_set>
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<vector<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) {

    tracker[vertex].discovery_time = tracker[vertex].lowest_reachable = ++timer;

    for(auto neighbor : adjacency_list[vertex]){

        if(parent[neighbor] != vertex){
            vertices_stack.push(vertex);

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

                parent[neighbor] = vertex;
                BCC(neighbor,parent,vertices_stack,tracker,timer);

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

                if(tracker[neighbor].lowest_reachable >= tracker[vertex].discovery_time){
                    biconnected_components.push_back(vector<int>());
                    vector<bool> pushed(vertices+1,false);
                    int n = biconnected_components.size();
                    int aux = vertices_stack.top();
                    while(aux!=vertex){
                        if(!pushed[aux]) {
                            biconnected_components[n - 1].push_back(aux);
                            pushed[aux] = true;
                        }
                        vertices_stack.pop();
                        aux = vertices_stack.top();
                    }
                    biconnected_components[n-1].push_back(vertex);
                }

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

    stack<int> vertices_stack;
    vector<int> parent(vertices + 1, -1);
    vector<Tracker> tracker(vertices + 1);

    int timer = 0;

    for (int i = 1; i < vertices + 1; i++) {
        if (parent[i] == -1) {
            parent[i] = i;
            BCC(i, parent, vertices_stack, tracker, timer);
        }
    }

    int num = biconnected_components.size();
    fout <<num<< '\n';

    for (int i = 0;i<num;i++) {
        for (int j=0;j<biconnected_components[i].size();j++)
            fout << biconnected_components[i][j] << ' ';
        fout << '\n';
    }
}

#pragma endregion