Cod sursa(job #3232720)

Utilizator MarcGrecMarc Grec MarcGrec Data 1 iunie 2024 10:19:29
Problema Componente biconexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <set>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

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

vector<vector<int>> graph;
vector<int> step;
vector<int> earliest;
int crtStep;
stack<pair<int, int>> edges;
vector<set<int>> components;

void init() {
    int n, m;
    fin >> n >> m;
    graph = vector<vector<int>>(n + 1);
    step = vector<int>(n + 1);
    earliest = vector<int>(n + 1);
    for (int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
}

void getComponent(int node, int nextNode) {
    components.emplace_back();
    pair<int, int> top;
    do {
        top = edges.top();
        edges.pop();
        components.back().insert(top.first);
        components.back().insert(top.second);
    } while (top.first != node || top.second != nextNode);
}

void dfs(int node, int prevNode) {
    earliest[node] = node;
    for (const int nextNode : graph[node]) {
        if (nextNode == prevNode) {
            continue;
        }
        if (step[nextNode] != 0) {
            earliest[node] = min(earliest[node], earliest[nextNode]);
            continue;
        }

        step[nextNode] = ++crtStep;
        edges.emplace(node, nextNode);
        dfs(nextNode, node);
        earliest[node] = min(earliest[node], earliest[nextNode]);

        if (earliest[nextNode] >= step[node]) {
            getComponent(node, nextNode);
        }
    }
}

int main() {
    init();
    for (size_t i = 1; i < graph.size(); ++i) {
        if (step[i] == 0) {
            step[i] = ++crtStep;
            dfs(i, 0);
        }
    }

    fout << components.size() << '\n';
    for (const auto &component : components) {
        for (int node : component) {
            fout << node << ' ';
        }
        fout << '\n';
    }
    return 0;
}

// vim: ai et sw=4 ts=4