Cod sursa(job #3373309)

Utilizator Cosor_AlexiaCosor Alexia Cosor_Alexia Data 6 noiembrie 2026 15:25:22
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

int n, m, i, j, cnt, timer, low[100002], tin[100002];
vector <int> a[100002];
vector <vector<int>> cb;
stack <int> st;

void DFS(int nod, int p = -1) {
    tin[nod] = low[nod] = ++timer;
    st.push(nod);
    for (auto it : a[nod]) {
        if (it == p)
            continue;
        if (tin[it])
            low[nod] = min(low[nod], tin[it]);
        else {
            DFS(it, nod);
            low[nod] = min(low[nod], low[it]);
            if (low[it] >= tin[nod]) {
                vector <int> v;
                int x;
                do {
                    x = st.top();
                    st.pop();
                    v.push_back(x);
                }
                while (x != it);
                v.push_back(nod);
                cb.push_back(v);
            }
        }
    }
}

int main()
{
    f >> n >> m;
    while (m--) {
        f >> i >> j;
        a[i].emplace_back(j);
        a[j].emplace_back(i);
    }
    for (int i = 1; i <= n; i++)
        if (!tin[i])
            DFS(i);
    g << cb.size() << endl;
    for (int i = 0; i < cb.size(); i++, g << "\n")
        for (auto it : cb[i])
            g << it << " ";

    return 0;
}