Cod sursa(job #2987067)

Utilizator maiaauUngureanu Maia maiaau Data 1 martie 2023 21:36:43
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

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

const int N = 1e5 + 5;

int n, k, low[N], niv[N];
bitset<N> u;
vector<int> v[N];
vector<vector<int>> comp;
stack<pair<int, int>> stk;

void read(), dfs(int, int, int), addcomp(int, int);

int main()
{
    read(); comp.pb({});
    dfs(1, 0, 0);
    g << k << '\n';
    for (int i = 1; i <= k; i++){
        sort(comp[i].begin(), comp[i].end());
        for (auto it: comp[i]) g << it << ' ';
        g << '\n';
    }
    
    return 0;
}

void read(){
    int m, x, y;
    f >> n >> m;
    for (; m; m--){
        f >> x >> y;
        v[x].pb(y); v[y].pb(x);
    }
}
void dfs(int nod, int tata, int h){
    u[nod] = 1;
    low[nod] = niv[nod] = h;
    for (auto it: v[nod]){
        if (it == tata) continue;
        if (u[it]) low[nod] = min(low[nod], niv[it]);
        else {
            stk.push({nod, it});
            dfs(it, nod, h + 1);
            low[nod] = min(low[nod], low[it]);
            if (low[it] >= niv[nod]){
                k++;
                addcomp(nod, it);
            }
            
        }
    }
}
void addcomp(int a, int b){
    comp.pb({}); 
    unordered_set<int> aux;
    int xx, yy;
    do {
        xx = stk.top().first; yy = stk.top().second; stk.pop();
        aux.insert(xx); aux.insert(yy);
    } while (xx != a || yy != b);
    for (auto it: aux) comp[k].pb(it);
}