Cod sursa(job #3220334)

Utilizator Maftei_TudorMaftei Tudor Maftei_Tudor Data 3 aprilie 2024 11:25:13
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

#define fi first
#define sc second

using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5;

int n, m, dpt[N], mindpt[N];
bool vzt[N];
vector<int> g[N];
stack<pii> stk;
vector<vector<int>> bcc;

void add(int a, int b) {
    bcc.push_back({});
    while(!stk.empty()) {
        int x = stk.top().fi, y = stk.top().sc;
        stk.pop();
        bcc.back().push_back(x);
        bcc.back().push_back(y);
        if((a == x && b == y) || (a == y && b == x))
            break;
    }

    sort(bcc.back().begin(), bcc.back().end());
    bcc.back().erase(unique(bcc.back().begin(), bcc.back().end()), bcc.back().end());
}
void dfs(int nod, int p) {
    dpt[nod] = dpt[p] + 1;
    mindpt[nod] = dpt[nod];
    vzt[nod] = 1;
    for(auto nxt : g[nod]) {
        if(nxt == p)
            continue;
        if(!vzt[nxt]) {
            stk.push({nod, nxt});
            dfs(nxt, nod);
            mindpt[nod] = min(mindpt[nod], mindpt[nxt]);
            if(mindpt[nxt] >= dpt[nod])
                add(nod, nxt);
        }
        else mindpt[nod] = min(mindpt[nod], dpt[nxt]);
    }
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    cin.tie(nullptr)->sync_with_stdio(0);

    cin >> n >> m;
    for(int i=1; i<=m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0);

    cout << bcc.size() << '\n';
    for(auto comp : bcc) {
        for(auto nod : comp)
            cout << nod << ' ';
        cout << '\n';
    }
    return 0;
}