Cod sursa(job #3374418)

Utilizator ryuuAdrian Rusu ryuu Data 9 noiembrie 2026 00:03:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.58 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

int main() {
    int n, m;
    fin >> n >> m;

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

    vector<int> idx(n + 1, 0), low(n + 1, 0), it(n + 1, 0);
    vector<int> stk, call;          // stk = stiva de noduri, call = stiva de apeluri DFS
    vector<vector<int> > comps;
    int timer = 0;

    for (int s = 1; s <= n; s++) {
        if (idx[s]) continue;

        idx[s] = low[s] = ++timer;
        stk.push_back(s);
        call.push_back(s);

        // DFS iterativ (evita depasirea stivei la N = 100000)
        while (!call.empty()) {
            int u = call.back();

            if (it[u] < (int)g[u].size()) {
                int v = g[u][it[u]++];
                if (!idx[v]) {
                    idx[v] = low[v] = ++timer;
                    stk.push_back(v);
                    call.push_back(v);
                } else {
                    low[u] = min(low[u], idx[v]);
                }
            } else {
                // am terminat u; ne intoarcem la parintele p
                call.pop_back();
                if (!call.empty()) {
                    int p = call.back();
                    low[p] = min(low[p], low[u]);

                    // din subarborele lui u nu se poate urca deasupra lui p:
                    // p separa subarborele lui u => am gasit o componenta biconexa
                    if (low[u] >= idx[p]) {
                        comps.push_back(vector<int>());
                        int w;
                        do {
                            w = stk.back();
                            stk.pop_back();
                            comps.back().push_back(w);
                        } while (w != u);
                        comps.back().push_back(p);   // p ramane pe stiva
                    }
                }
            }
        }
        stk.clear();
    }

    // afisare canonica: noduri sortate in componente, componentele sortate
    for (int i = 0; i < (int)comps.size(); i++)
        sort(comps[i].begin(), comps[i].end());
    sort(comps.begin(), comps.end());

    fout << comps.size() << "\n";
    for (int i = 0; i < (int)comps.size(); i++) {
        for (int j = 0; j < (int)comps[i].size(); j++) {
            if (j) fout << " ";
            fout << comps[i][j];
        }
        fout << "\n";
    }
    return 0;
}