Cod sursa(job #2408044)

Utilizator Constantin.Dragancea Constantin Constantin. Data 17 aprilie 2019 15:47:56
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define smin(X, Y) ((X) < (Y) ? (X) : (Y))
int n, m, low[N], ord[N], k, cnt, st[N], vf, cp;
vector <int> v[N], comp[N];

void dfs(int q, int pr){
    low[q] = ord[q] = ++k;
    st[++vf] = q;
    for (auto it: v[q]){
        if (it == pr) continue;
        if (!ord[it]){
            if (pr == -1) cnt++;
            dfs(it, q);
            low[q] = smin(low[q], low[it]);
            if (low[it] >= ord[q]){
                while (st[vf] != q) comp[cp].push_back(st[vf--]);
                comp[cp].push_back(q);
                cp++;
            }
        }
        else low[q] = smin(low[q], ord[it]);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ifstream cin ("biconex.in");
    ofstream cout ("biconex.out");
    cin >> n >> m;
    for (int i=0, x, y; i<m; i++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, -1);
    cout << cp << '\n';
    for (int i=0; i<cp; i++, cout << '\n'){
        sort(comp[i].begin(), comp[i].end());
        for (auto it: comp[i]) cout << it << ' ';
    }
    return 0;
}