Cod sursa(job #2528536)

Utilizator piroComisia piro Data 22 ianuarie 2020 05:32:25
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;

ifstream ccin("biconex.in");
ofstream ccout("biconex.out");

int biconex(int x, int l, vector<vector<int>>& G,
                    vector<int>& s,
                    vector<int>& T, vector<int>& L,
                    vector<vector<int>>& ans) {
    int hx = L[x] = l;
    s.push_back(x);
    for (auto it : G[x]) if (it != T[x]) {
        if (!L[it]) {
            int save = s.size();
            T[it] = x;
            int hit = biconex(it, l+1, G, s, T, L, ans);
            if (hit >= l) {
                ans.push_back(vector<int>());
                while (s.size() != save) {
                    ans.back().push_back(s.back());
                    s.pop_back();
                }
                ans.back().push_back(x);
            }
            hx = min(hx, hit);
        }
        else hx = min(hx, L[it]);
    }
    return hx;
}

int main() {
    int n, m; ccin >> n >> m;
    vector<vector<int>> G(n + 1), ans;
    vector<int> T(n + 1), L(n + 1), s;

    for (int i = 1; i <= m; i++) {
        int x, y; ccin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    biconex (1, 1, G, s, T, L, ans);

    ccout << ans.size() << '\n';
    for (auto& it : ans) {
        sort(it.begin(), it.end());
        for (auto jt : it) ccout << jt << ' ';
        ccout << '\n';
    }
    return 0;
}