Cod sursa(job #2987058)

Utilizator maiaauUngureanu Maia maiaau Data 1 martie 2023 21:32:45
Problema Componente biconexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 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;
    
    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({}); k++;
    unordered_set<int> aux;
    int xx, yy;
    do {
        xx = stk.top().first; yy = stk.top().second;
        aux.insert(xx); aux.insert(yy);
    } while (xx != a || yy != b);
    for (auto it: aux) comp[k].pb(it);
}