Cod sursa(job #3371650)

Utilizator IeremiaNicolaescu Ieremia Ieremia Data 31 octombrie 2026 11:13:53
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NMAX = 100005;

vector<int> g[NMAX];
vector<pair<int, int>> stiva;
vector<int> ctc[NMAX];

int lvl[NMAX], low[NMAX];
int in_comp[NMAX];
int timer, nr_ctc;

void dfs(int u, int p) {
    lvl[u] = low[u] = ++timer;

    for (int v : g[u]) {
        if (v == p) continue; 


        if (lvl[v] < lvl[u]) {
            stiva.push_back({u, v});

            if (!lvl[v]) { 
                dfs(v, u);

                low[u] = min(low[u], low[v]);

                if (low[v] >= lvl[u]) {
                    nr_ctc++;

                    while (!stiva.empty()) {
                        auto edge = stiva.back();
                        stiva.pop_back();

                        int x = edge.first;
                        int y = edge.second;

                        if (in_comp[x] != nr_ctc) {
                            in_comp[x] = nr_ctc;
                            ctc[nr_ctc].push_back(x);
                        }
                        if (in_comp[y] != nr_ctc) {
                            in_comp[y] = nr_ctc;
                            ctc[nr_ctc].push_back(y);
                        }

                        if (x == u && y == v) break;
                    }
                }
            } else { 
                low[u] = min(low[u], lvl[v]);
            }
        }
    }
}

int main() {
    int n, m;
    if (!(fin >> n >> m)) return 0;

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

    fout << nr_ctc << "\n";
    for (int i = 1; i <= nr_ctc; i++) {
        for (int v : ctc[i]) {
            fout << v << " ";
        }
        fout << "\n";
    }

    return 0;
}