Cod sursa(job #3230301)

Utilizator cristianc90210Cristian Constantin cristianc90210 Data 20 mai 2024 14:46:31
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
//
// Created by Cristian Constantin on 20.05.2024.
//
#include <bits/stdc++.h>
using namespace std;

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

int n, m, root = 1, rootChildren;
vector<vector<int>> graph;
vector<bool> visited;
vector<int> depth, low;
stack<pair<int, int>> edges;
vector<vector<int>> biconnectedComponents;

void initialize() {
    graph.resize(n + 1);
    visited.resize(n + 1, false);
    depth.resize(n + 1);
    low.resize(n + 1);
}

void readInput() {
    fin >> n >> m;
    initialize();
    int u, v;
    for (int i = 0; i < m; ++i) {
        fin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}

void addBiconnectedComponent(int u, int v) {
    vector<int> component;
    pair<int, int> edge;
    do {
        edge = edges.top();
        edges.pop();
        component.push_back(edge.first);
        component.push_back(edge.second);
    } while (!(edge.first == u && edge.second == v));
    sort(component.begin(), component.end());
    component.erase(unique(component.begin(), component.end()), component.end());
    biconnectedComponents.push_back(component);
}

void dfs(int u, int parent) {
    visited[u] = true;
    depth[u] = low[u] = (parent == -1 ? 0 : depth[parent] + 1);
    for (int v : graph[u]) {
        if (v == parent) continue;
        if (visited[v]) {
            low[u] = min(low[u], depth[v]);
        } else {
            edges.push({u, v});
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= depth[u]) {
                addBiconnectedComponent(u, v);
            }
        }
    }
}

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

int main() {
    readInput();
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            root = i;
            rootChildren = 0;
            dfs(i, -1);
        }
    }
    printBiconnectedComponents();
    return 0;
}