Cod sursa(job #2795840)

Utilizator popaandaioanaPopa Anda-Ioana popaandaioana Data 7 noiembrie 2021 01:58:53
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.83 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;

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

class graf_neorientat
{
    int n, m; //n = nr. noduri m = nr. muchii
public:
    vector <int> lista[100005]; //in acest mod va fi stocat graful
    stack <int> stiva;
    int niv[100005], niv_ma[100005], numar_cb = 0;
    vector <int> rezultat[100005];
    graf_neorientat(int, int);
    void construire_graf_neorientat();
    void dfs_comp_biconexe(int, int, int);
    int comp_biconexe(int, int);
};

graf_neorientat::graf_neorientat(int n, int m)
{
    this -> n = n;
    this -> m = m;
}

void graf_neorientat :: construire_graf_neorientat()
{
    for(int i = 0; i < m; i ++) //parcurgem muchiile
    {
        int u, v;
        in >> u >> v; //citim nodurile intre care exista muchie
        lista[u].push_back(v);
                                //marcam in lista de 2 ori, fiind neorientat
        lista[v].push_back(u);
    }
}

int graf_neorientat :: comp_biconexe(int nod, int i)
{
    numar_cb ++; //numara comp. biconexe
    //elim. din stiva toate nodurile pana la i inclusiv si le punem in vectorul rezultat
    //eliminarea nu se face pana la nod deoarece intre i si nod mai pot exista noduri care apartin altei comp. biconexe
    while(stiva.top() != i)
    {
        rezultat[numar_cb].push_back(stiva.top());
        stiva.pop();
    }
    rezultat[numar_cb].push_back(nod);
    rezultat[numar_cb].push_back(i);
    stiva.pop();
}

void graf_neorientat :: dfs_comp_biconexe(int nod, int nivel, int tata) //nod = nodul curent; nivel = niv. nodului; tata = tatal lui nod
{
    niv_ma[nod] = nivel; //niv_ma[nod] = nivelul minim accesibil la care se poate ajunge din nod, mergand pe muchii de arbore, ultima muchie = de intoarcere
    niv[nod] = nivel; //niv[nod] = nivelul nodului nod
    stiva.push(nod); //in stiva se pun nodurile in ordinea parcurgerii in dfs
    for(auto i : lista[nod]) //pentru fiecare nod din lista de adiacenta a nodului curent
    {
        if(!niv[i]) //daca nu a fost vizitat
        {
            dfs_comp_biconexe(i ,nivel + 1, nod); //apelare recursiva pentru fiecare nod i adiacent cu nodul curent
            niv_ma[nod] = min(niv_ma[i], niv_ma[nod]); //calculeaza nivelul minim accesibil al nodului curent
            if(niv_ma[i] >= nivel) //am gasit punct de articulatie
                comp_biconexe(nod, i); //construieste componenta biconexa
            //------------------------------------------
            /*if(niv[nod] <= niv_ma[i] && niv[nod] != 1)
                out << nod << " " << "este punct de articulatie" << endl;
            //------------------------------------------
            if(niv[nod] < niv_ma[i]) //afisarea muchiilor critice(critical connection)
            {
                muchii_critice.push_back(make_pair(nod, i));
            }*/
        }
        else if(i != tata) //daca nodul a fost viz. dar e diferit de tatal lui nod => (nod, i) = muchie de intoarcere
            niv_ma[nod] = min(niv_ma[nod], niv[i]); //actualizam nivelul minim accesibil al lui nod
    }
}

int main()
{

	int n, m;
    in >> n >> m; //se citesc nr. de noduri, nr. de muchii
	graf_neorientat G(n, m);
    G.construire_graf_neorientat();
	for(int i = 1; i <= n; i ++)
        	if(!G.niv[i]) //pentru fiecare nod nevizitat
            		G.dfs_comp_biconexe(i,1,0);
    	/*out << "Muchii crtice : " << endl;
    	for (int i = 0; i < G.muchii_critice.size(); i ++)
    	{
        	out << G.muchii_critice[i].first << " "
             	<< G.muchii_critice[i].second << endl;
    	}*/

    	out << "Nr. comp biconexe: " << G.numar_cb << '\n';
    	out << "Comp. biconexe: " << endl;
    	for(int i = 1; i <= G.numar_cb; i ++,cout << '\n')
        	for(auto j : G.rezultat[i])
            		out << j << " ";

}