Cod sursa(job #3332487)

Utilizator alex_codeTrifanescu Alexandru alex_code Data 6 ianuarie 2026 22:31:21
Problema Componente biconexe Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.74 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <set>
#include <queue>
#include <stack>
int n, m, idx[1001], low[1001], nr_lot;
bool estePunct[1001]={false};
std::vector<int>v[1001];
std::stack<std::pair<int, int>>sta;
int ceas;
std::vector<int>ob[1001];
std::ifstream fin("biconex.in");
std::ofstream gin("biconex.out");

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;

                    }
                    nr_lot++;
                    for(int ele :noduri_componenta){
                        ob[nr_lot].push_back(ele);
                    }

                }

            }
            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;
    fin >> n >> m;
    for(i=1; i<=m; ++i){
        fin >> 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);
        }
    }

    gin << nr_lot << "\n";
    for(i=1; i<=nr_lot; ++i, gin << "\n"){
        std::sort(ob[i].begin(), ob[i].end());
        for(const auto elem:ob[i]){
            gin << elem << " ";
        }
    }

    return 0;
}