Cod sursa(job #3282011)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 4 martie 2025 11:57:51
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <array>

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

const int MAX_N = 100000;
const int MAX_M = 200000;

int n, m;
std::vector<int> g1[MAX_N + 1];
std::vector<int> g2[MAX_N + 1];

std::vector<std::array<int, 2>> g_init[MAX_N + 1];
std::vector<std::array<int, 2>> edges;

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

bool vis_edge[MAX_M + 1];
bool vis[MAX_N + 1];

void dfs_init(int node) {
    vis[node] = true;
    for (auto [to, idx] : g_init[node]) {
        if (!vis_edge[idx]) {
            g1[node].push_back(to);
            g2[to].push_back(node);
            vis_edge[idx] = true;
        }
        if (!vis[to])
            dfs_init(to);
    }
}

std::stack<int> stk;

void dfs1(int node) {
    vis[node] = true;
    for (int to : g1[node])
        if (!vis[to])
            dfs1(to);
    stk.push(node);
}

std::vector<int> comp;
std::vector<std::vector<int>> comps;
int id[MAX_N + 1], cnt;

void dfs2(int node) {
    id[node] = cnt;
    vis[node] = true;
    comp.push_back(node);
    for (int to : g2[node])
        if (!vis[to])
            dfs2(to);
}

void reset_vis() {
    for (int i = 1; i <= n; i++)
        vis[i] = false;
}

void solve() {
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs_init(i);

    reset_vis();

    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs1(i);

    reset_vis();

    while (!stk.empty()) {
        int node = stk.top();
        stk.pop();

        if (vis[node])
            continue;

        comp.clear();
        cnt++;
        dfs2(node);

        if (comp.size() > 1)
            comps.push_back(comp);
    }

    for (auto [x, y] : edges)
        if (id[x] != id[y])
            comps.push_back({x, y});

    fout << comps.size() << '\n';

    for (const auto & comp : comps) {
        for (int x : comp)
            fout << x << ' ';
        fout << '\n';
    }
}

int main() {
    read();
    solve();
    return 0;
}