Cod sursa(job #3373048)

Utilizator robertbaciuBaciu Vlad-Robert robertbaciu Data 5 noiembrie 2026 22:52:38
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bitset>
#include <fstream>
#include <set>
#include <stack>
#include <vector>

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

int const NMAX = 100000;

std::vector<std::vector<int>> graph;
std::bitset<NMAX + 1> visited;
std::vector<int> lvl;
std::vector<int> ret_lvl;
std::stack<std::pair<int, int>> stack;
std::vector<std::set<int>> comps;

void dfs(int i) {
    visited[i] = 1;
    ret_lvl[i] = lvl[i];

    for (int j : graph[i]) {
        if (!visited[j]) {
            stack.push({i, j});

            lvl[j] = lvl[i] + 1;

            dfs(j);

            ret_lvl[i] = std::min(ret_lvl[i], ret_lvl[j]);

            if (ret_lvl[j] >= lvl[i]) {
                std::set<int> comp;

                while (!stack.empty()) {
                    auto edge = stack.top();
                    stack.pop();

                    comp.insert(edge.first);
                    comp.insert(edge.second);

                    if (edge.first == i && edge.second == j) {
                        break;
                    }
                }

                comps.push_back(comp);
            }
        } else if (lvl[j] < lvl[i] - 1) {
            stack.push({i, j});

            ret_lvl[i] = std::min(ret_lvl[i], lvl[j]);
        }
    }
}

int main(int argc, char *argv[]) {
    int n, m;
    fin >> n >> m;

    graph.resize(n + 1);
    lvl.resize(n + 1);
    ret_lvl.resize(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);
    }

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            lvl[i] = 1;
            dfs(i);
        }
    }

    fout << comps.size() << '\n';
    for (auto &comp : comps) {
        for (int node : comp) {
            fout << node << ' ';
        }
        fout << '\n';
    }

    return 0;
}