Cod sursa(job #3203914)

Utilizator andiRTanasescu Andrei-Rares andiR Data 15 februarie 2024 01:03:35
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>

#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
typedef long long ll;
const ll Nmax=1e5+5, inf=1e9+5;

int n, m, nrc;
vector <int> ad[Nmax]; //lista de adiacenta
int h[Nmax], reach[Nmax]; // inaltimea nodului in arborele dfs; inaltimea minima la care poate ajunge printr-un drum
stack <int> st; //stiva componentelor biconexe
vector <int> sol[Nmax]; //lista componentelor biconexe
void dfs(int nod, int p){
    h[nod]=h[p]+1;
    reach[nod]=h[nod]; // initializam nivelul minim la care putem ajunge cu nivelul curent
    st.push(nod);
    for (auto it:ad[nod]) // iteram prin vecinii nodului curent
        if (it!=p) // daca vecinul nu este tata
            if (!h[it]){ // daca fiul nu e vizitat
                dfs(it, nod);
                reach[nod]=min(reach[nod], reach[it]); // updatam reach-ul
                if (reach[it]>=h[nod]){ // daca reach-ul fiului nu trece de inaltimea nodului avem componenta biconexa
                    while (st.top()!=it){
                        sol[nrc].pb(st.top());
                        st.pop();
                    }
                    sol[nrc].pb(st.top());
                    sol[nrc].pb(nod);
                    st.pop();
                    nrc++;
                }
            }
            else reach[nod]=min(reach[nod], h[it]); // updatam reach-ul
}
inline void hopcraft_tarjan(){
    for (int i=0; i<n; i++)
        if (!h[i]) // calculam componentele biconexe pt fiecare componenta conexa
            dfs(i, i);
}
int main()
{
    fin>>n>>m;
    int a, b;
    for (int i=0; i<m; i++){
        fin>>a>>b;
        a--; b--; // indexam nodurile de la 0
        ad[a].pb(b);
        ad[b].pb(a);
    }
    hopcraft_tarjan();
    fout<<nrc<<'\n';
    for (int i=0; i<nrc; i++){ // afisam componentele biconexe
        for (auto it:sol[i])
            fout<<it+1<<' ';
        fout<<'\n';
    }
    return 0;
}