Cod sursa(job #3209200)

Utilizator razvan242Zoltan Razvan-Daniel razvan242 Data 2 martie 2024 10:42:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.38 kb
#include <bits/stdc++.h>

using namespace std;

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

int task;
int numberOfVertices, numberOfEdges;
int root = 1;
int sonsOfRoot;
vector <vector <int>> graph;
vector <bool> visited;
vector <int> level, minimumLevel;
stack <pair <int, int>> edgeStack;
vector <unordered_set <int>> biconnectedComponents;

void initializeContainers() {
    graph = vector <vector <int>>(numberOfVertices + 1);
    visited = vector <bool>(numberOfVertices + 1, false);
    level = vector <int>(numberOfVertices + 1);
    minimumLevel = vector <int>(numberOfVertices + 1);
}

void readData() {
    fin >> numberOfVertices >> numberOfEdges;
    initializeContainers();

    int x, y;
    while (numberOfEdges--) {
        fin >> x >> y;
        graph[x].emplace_back(y);
        graph[y].emplace_back(x);
    }
}

void extractBiconnectedComponent(int node, int neighbour) {
    unordered_set <int> biconnectedComponent;
    pair <int, int> edge;
    do {
        edge = edgeStack.top();
        edgeStack.pop();
        biconnectedComponent.insert(edge.first);
        biconnectedComponent.insert(edge.second);
    } while (edge.first != node && edge.second != neighbour);
    biconnectedComponents.emplace_back(biconnectedComponent);
}

void dfs(int node, int father) {
    visited[node] = true;
    level[node] = level[father] + 1;
    minimumLevel[node] = level[father] + 1;

    for (const int& neighbour: graph[node]) {
        if (neighbour == father) {
            continue;
        }

        if (visited[neighbour]) {
            minimumLevel[node] = min(minimumLevel[node], level[neighbour]);
        }
        else {
            if (node == root) {
                ++sonsOfRoot;
            }
            edgeStack.emplace(node, neighbour);
            dfs(neighbour, node);
            minimumLevel[node] = min(minimumLevel[node], minimumLevel[neighbour]);

            if (minimumLevel[neighbour] >= level[node]) {
                extractBiconnectedComponent(node, neighbour);
            }
        }
    }
}

void printBiconnectedComponents() {
    fout << biconnectedComponents.size() << '\n';
    for (const auto& biconnectedComponent: biconnectedComponents) {
        for (const int& node: biconnectedComponent) {
            fout << node << ' ';
        }
        fout << '\n';
    }
}

int main()
{
    readData();
    dfs(root, 0);
    printBiconnectedComponents();
    return 0;
}