Cod sursa(job #3376274)

Utilizator Ilinca_Radu_2022Radu Ilinca-Rucsandra Ilinca_Radu_2022 Data 17 noiembrie 2026 10:31:00
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

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

const int MAXN = 2e5 + 5;

int in[MAXN], low[MAXN], lvl, k;
vector<pair<int, int>> st;
unordered_set<int> comp[MAXN];
int n, m;
vector<int> v[MAXN];

void dfs(int node) {
    lvl++;
    in[node] = lvl;
    low[node] = lvl;
    
    for (auto x: v[node]) {
        if (in[x] == 0) {
            st.push_back({node, x});
            dfs(x);
            low[node] = min(low[node], low[x]);

            if (low[x] == in[node]) {
                k++;
                while (st.back() != make_pair(node, x)) {
                    comp[k].insert(st.back().fi);
                    comp[k].insert(st.back().se);
                    st.pop_back();
                }
                comp[k].insert(node);
                comp[k].insert(x);
                st.pop_back();
            }

        } else {
            low[node] = min(low[node], in[x]);
        }
    }    

    lvl--;
}

int main() {
    int x, y;

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

    lvl = 0;
    dfs(1);

    fout << k << "\n";
    for (int i = 1; i <= k; i++) {
        for (auto x: comp[i]) {
            fout << x << " ";
        }
        fout << "\n";
    }
    return 0;
}