Cod sursa(job #3188468)

Utilizator AlessiaFrunzaAlessia Frunza AlessiaFrunza Data 3 ianuarie 2024 00:33:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.62 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

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

void formeaza_rezultat(int primul, int ultimul, stack<pair<int, int>>& muchii_componenta, vector<vector<int>>& componenta_biconexa) {
    set<int> component_set;
    vector<int> component;
    pair<int, int> muchie;

    do {
        muchie = muchii_componenta.top(); muchii_componenta.pop();
        component_set.insert(muchie.first);
        component_set.insert(muchie.second);
    } while (muchie != make_pair(primul, ultimul) && muchie != make_pair(ultimul, primul));

    component.assign(component_set.begin(), component_set.end());
    componenta_biconexa.push_back(component);
}

void dfs(int nod_curent, int parinte, const vector<vector<int>>& lista_vecini, int discovery_time[], int lowest[], bool vizitate[], stack<pair<int, int>>& muchii_componenta, vector<vector<int>>& componenta_biconexa) {
    static int timeCounter = 0;
    vizitate[nod_curent] = true;
    discovery_time[nod_curent] = lowest[nod_curent] = ++timeCounter;  
     
    for (int vecin : lista_vecini[nod_curent]) {
        if (vecin != parinte) {
            if (!vizitate[vecin]) {
                muchii_componenta.push({nod_curent, vecin});
                dfs(vecin, nod_curent, lista_vecini, discovery_time, lowest, vizitate, muchii_componenta, componenta_biconexa);
                lowest[nod_curent] = min(lowest[nod_curent], lowest[vecin]);
                if (lowest[vecin] >= discovery_time[nod_curent]) {
                    formeaza_rezultat(vecin, nod_curent, muchii_componenta, componenta_biconexa);
                }
            } else {
                lowest[nod_curent] = min(lowest[nod_curent], discovery_time[vecin]);
            }
        }
    }
}

int main() {
    int numar_noduri, numar_muchii;
    fin >> numar_noduri >> numar_muchii;
    
    vector<vector<int>> lista_vecini(numar_noduri + 1);
    int discovery_time[100000] = {0}, lowest[100000] = {0};
    bool vizitate[100000] = {false};
    vector<vector<int>> componenta_biconexa;
    stack<pair<int, int>> muchii_componenta;

    for (int i = 0; i < numar_muchii; i++) {
        int nod1, nod2;
        fin >> nod1 >> nod2;
        lista_vecini[nod1].push_back(nod2);
        lista_vecini[nod2].push_back(nod1);
    }

    dfs(1, 0, lista_vecini, discovery_time, lowest, vizitate, muchii_componenta, componenta_biconexa);

    fout << componenta_biconexa.size() << '\n';
    
    for (const auto& comp : componenta_biconexa) {
        for (int nod : comp) {
            fout << nod << ' ';
        }
        fout << '\n';
    }

    return 0;
}