Cod sursa(job #3188463)

Utilizator AlessiaFrunzaAlessia Frunza AlessiaFrunza Data 3 ianuarie 2024 00:11:20
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

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) {
    vector<int> component;
    pair<int, int> muchie;
    do {
        muchie = muchii_componenta.top(); muchii_componenta.pop();
        component.push_back(muchie.first);
        component.push_back(muchie.second);
    } while (muchie != make_pair(primul, ultimul) && muchie != make_pair(ultimul, primul));
    componenta_biconexa.push_back(component);
}

void dfs(int nod_curent, int parinte, vector<vector<int>> lista_vecini, int discovery_time[], int lowest[], bool vizitate[], stack<pair<int, int>>& muchii_componenta, vector<vector<int>>& componenta_biconexa) {
    vizitate[nod_curent] = true;
    lowest[nod_curent] = discovery_time[nod_curent];   
    for (int vecin : lista_vecini[nod_curent]) {
        if (vecin != parinte) {
            if (discovery_time[nod_curent] > discovery_time[vecin]) {
                muchii_componenta.push({nod_curent, vecin});
            }
            if (!vizitate[vecin]) {
                discovery_time[vecin] = discovery_time[nod_curent] + 1;
                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 if (vecin != parinte) {
                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], lowest[100000];
    bool vizitate[100000];
    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);
    }

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

    cout << componenta_biconexa.size() << '\n';
    for (vector<int> comp : componenta_biconexa) {
        vector<bool> printat_deja(numar_noduri, false);
        for (int nod : comp) {
            if (!printat_deja[nod]) {
                fout << nod << ' ';
                printat_deja[nod] = true;
            }
        }
        fout << '\n';
    }

    return 0;
}