Cod sursa(job #3372799)

Utilizator laurentiu.maticaMatica Laurentiu-Andrei laurentiu.matica Data 5 noiembrie 2026 00:42:10
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

int cnt;

stack<pair<int,int>> s;
vector<vector<int>> g;
vector<set<int>> cbc;
vector<int> t;
vector<int> l;
vector<int> v;
vector<int> c;

void dfs(const int n, const int m) {
    t[n] = l[n] = ++cnt;
    v[n] = 1;
    int copii = 0;
    for (const auto x: g[n]) {
        if (!v[x]) {
            s.emplace(n, x);
            dfs(x,  n);
            copii++;
            l[n] = min(l[n],l[x]);
            if (l[x] >= t[n]) {
                if (m != -1) {
                    c[n] = 1;
                }
                cbc.emplace_back();
                while (s.top() != make_pair(n,x)) {
                    cbc.back().insert(s.top().second);
                    s.pop();
                }
                cbc.back().insert(s.top().second);
                s.pop();
                cbc.back().insert(n);
            }
        }
        else if (x != m && t[x] < t[n]) {
            l[n] = min(l[n],t[x]);
            s.emplace(n, x);
        }
    }
    if (m == -1 && copii >= 2) {
        c[n] = 1;
    }
}

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

    g.resize(n+1);
    t.resize(n+1,0);
    l.resize(n+1,0);
    v.resize(n+1,0);
    c.resize(n+1,0);

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

    for (int i=1;i<=n;i++) {
        if (!v[i]) {
            dfs(i, -1);
        }
    }

    cout << static_cast<int>(cbc.size()) << '\n';
    for (const auto &x: cbc) {
        for (const auto y: x) {
            cout << y << ' ';
        }
        cout << '\n';
    }

    return 0;
}