Cod sursa(job #3332479)

Utilizator alex_codeTrifanescu Alexandru alex_code Data 6 ianuarie 2026 21:56:18
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.56 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <set>
#include <queue>
#include <stack>
int n, m, idx[1001], low[1001];
bool estePunct[1001]={false};
std::vector<int>v[1001];
std::stack<std::pair<int, int>>sta;
int ceas;

void Tarjan_PDA(int nod, int tata){
    int i, e, s, cont=0, nr_copii=0;
    idx[nod]=low[nod]=++ceas;

    for(const auto element:v[nod]){
        if(element==tata)continue;
        else{
            if(idx[element]==0){
                nr_copii++;
                sta.push({nod, element});
                Tarjan_PDA(element, nod);
                low[nod]=std::min(low[nod], low[element]);

                if(low[element]>=idx[nod]){
                    if(tata!=-1)estePunct[nod]=true;

                    std::vector<int> noduri_componenta;
                    bool viz_local[1001]={false};

                    while(true){
                        std::pair<int, int> muchie = sta.top();
                        sta.pop();

                        if (!viz_local[muchie.first]) {
                            noduri_componenta.push_back(muchie.first);
                            viz_local[muchie.first] = true;
                        }
                        if (!viz_local[muchie.second]) {
                            noduri_componenta.push_back(muchie.second);
                            viz_local[muchie.second] = true;
                        }

                        if(muchie.first==nod && muchie.second==element)break;

                    }

                    std::cout << "Componenta : ";
                    for(int ele :noduri_componenta)
                        std::cout << ele << " ";
                    std::cout << "\n";

                }

            }
            else{
                if(element!=tata && idx[element] < idx[nod]){
                    sta.push({nod, element});
                }
                if(idx[element]!=0){
                    low[nod]=std::min(low[nod], idx[element]);
                }
            }
        }

    }
    if(tata==-1 && nr_copii>1)estePunct[nod]=true;

}


int main(){

    int i, e, s, cont=0, a, b, nr_puncte=0;
    std::cin >> n >> m;
    for(i=1; i<=m; ++i){
        std::cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(i=1; i<=n; ++i)
    {
        if(idx[i]==0){
            Tarjan_PDA(i, -1);
        }
    }

    for(i=1; i<=n; ++i)
        if(estePunct[i]==true)std::cout << i << " ";
    std::cout << "\n";


    return 0;
}