Cod sursa(job #3152324)

Utilizator andiRTanasescu Andrei-Rares andiR Data 24 septembrie 2023 17:08:31
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.3 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 lvl[Nmax];
bool vis[Nmax];
stack <int> st; //stiva componentelor biconexe
vector <int> sol[Nmax]; //lista componentelor biconexe
int dfs(int nod, int p){
    if (vis[nod]) ///daca am trecut deja prin nod returnam nivelul
        return lvl[nod];
    vis[nod]=1;
    lvl[nod]=lvl[p]+1;
    st.push(nod);
    int mn=lvl[nod]; ///initializam nivelul minim la care putem ajunge cu nivelul curent
    for (auto it:ad[nod]){ ///iteram prin vecinii nodului curent
        int crt;
        bool ok=vis[it];
        if (it!=p){ ///daca vecinul nu este tata
            crt=dfs(it, nod); ///atunci updatam minimul curent
            mn=min(mn, crt);
            if (!ok && crt>=lvl[nod]){ ///daca vecinul nu este vizitat si nivelul minim al sau este mai mare sau egal cu cel curent
                while (st.top()!=it){ /// atunci se initializeaza o noua componenta biconexa
                    sol[nrc].pb(st.top());
                    st.pop();
                }
                sol[nrc].pb(st.top());
                sol[nrc].pb(nod);
                st.pop();
                nrc++;
            }
        }
    }
    return mn; ///returnam nivelul minim la care se poate ajunge pornind din nodul curent
}
inline void hopcraft_tarjan(){
    lvl[n]=-1;
    for (int i=0; i<n; i++)
        if (!vis[i]) ///calculam componentele biconexe pt fiecare componenta conexa
            dfs(i, n);
}
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;
}