Cod sursa(job #3373236)

Utilizator srares2006Samoila Rares srares2006 Data 6 noiembrie 2026 13:10:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.57 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

const int MAXN = 100005;

vector<int> vecini[MAXN]; // nodurile legate direct de x
bool vizitat[MAXN];
int nivel[MAXN]; // adancimea lui x in arbore
int low[MAXN]; // cel mai mic nivel unde poti sa cobori si ai muchie sa te intorci
vector<pair<int,int>> stiva; // muchiile care nu sunt dintr-o componenta biconexa inca
vector<vector<int>> componente; // lista cu nodurile unei componente
int ultimaComponenta[MAXN]; // in ce componenta a fost pus ultima oara x sa nu fie de 2 ori in acelasi loc

void extrageComponenta(int x, int y){
    vector<int> noduri; 
    int numarComponenta= componente.size() + 1;
    while(!stiva.empty()){
        int a = stiva.back().first;
        int b = stiva.back().second;
        stiva.pop_back();
        if(ultimaComponenta[a] != numarComponenta)
        {
            noduri.push_back(a);
            ultimaComponenta[a] = numarComponenta;
        }
        if(ultimaComponenta[b] != numarComponenta)
        {
            noduri.push_back(b);
            ultimaComponenta[b] = numarComponenta;
        }

        if(a == x && b == y)
            break; // ne-am intors la start 
    }
    componente.push_back(noduri);
}

void dfs(int x, int parinte){
    vizitat[x] = true;
    low[x]= nivel[x]; // poate ajunge doar pana la propriu nivel in start
    for(int y : vecini[x])
    {
        if(y == parinte) // ignor muchia prin care am venit
            continue;
        if(!vizitat[y]){
            stiva.push_back({x,y});
            nivel[y]=nivel[x]+1;
            dfs(y,x);
            low[x] = min(low[x],low[y]); // actualizam ramura
            if(low[y] >= nivel[x]){
                extrageComponenta(x,y);
            }
        }
        else if(nivel[y]< nivel[x]){ // y este deja vizitat si este si mai sus decat x 
            stiva.push_back({x,y});// muchie de intoarcere
            low[x] = min(low[x],nivel[y]);
        }
    }
}

int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {int x,y;
        fin>>x>>y;
        vecini[x].push_back(y);
        vecini[y].push_back(x);
    }
    for(int x=1;x<=n;x++)
    {
        if(!vizitat[x]){
            nivel[x]=0;
            dfs(x,0);
        }
    }
    fout<<componente.size()<<'\n';
    for(const vector<int>& componenta : componente){
        for(int nod: componenta){
            fout<<nod<<" ";
        }
        fout<<'\n';
    }
    return 0;
}