Cod sursa(job #3374626)

Utilizator aspaNadu Tudor aspa Data 9 noiembrie 2026 06:22:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>
using namespace std;

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

vector<int> A[100001];
vector<vector<int>> components;
vector<pair<int, int>> st;
int visited[100001];
int level[100001];
int low[100001];
int mark[100001];

void pop_component(int k, int n) {
    vector<int> component;
    int c = components.size() + 1;

    pair<int, int> e;
    do {
        e = st.back();
        st.pop_back();

        if (mark[e.first] != c) {
            mark[e.first] = c;
            component.push_back(e.first);
        }
        if (mark[e.second] != c) {
            mark[e.second] = c;
            component.push_back(e.second);
        }
    } while (e != make_pair(k, n));

    components.push_back(component);
}

void dfs(int k, int parent) {
    visited[k] = 1;
    low[k] = level[k];

    for (auto n : A[k]) {
        if (n == parent)
            continue;

        if (visited[n]) {
            if (level[n] < level[k]) {
                st.push_back({k, n});
                low[k] = min(low[k], level[n]);
            }
            continue;
        }

        level[n] = level[k] + 1;
        st.push_back({k, n});
        dfs(n, k);

        low[k] = min(low[k], low[n]);

        if (low[n] >= level[k])
            pop_component(k, n);
    }
}

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

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

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

    fout << components.size() << "\n";
    for (auto &component : components) {
        for (auto v : component)
            fout << v << " ";
        fout << "\n";
    }

    return 0;
}