Pagini recente » Cod sursa (job #335781) | Cod sursa (job #1934188) | Cod sursa (job #1638635) | Cod sursa (job #2580689) | Cod sursa (job #3272135)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#define maxi 100001
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
stack<pair<int, int>> stivaComponenteBiconexe; // Stiva pentru muchii din componenta biconexa
vector<set<int>> componenteBiconexe; // Vector de componente biconexe
class Graf {
int nrNoduri, nrMuchii; // Numarul de noduri si muchii din graf
int x, y; // Nodurile unei muchii (x, y)
int vizitat[maxi] = {0}; // Vector pentru a marca nodurile vizitate
int niv_min[maxi] = {0}; // Nivelul minim pentru fiecare nod
vector<int> *adiacenta; // Lista de adiacenta pentru graful neorientat
public:
Graf();
~Graf();
void citireDFS(); // Citirea grafului neorientat
void biconex(int nodPlecare, int precedent, int k); // Determinarea componentelor biconexe
void afisareComponenteBiconexe(); // Afisarea componentelor biconexe
};
Graf::Graf() {
nrNoduri = nrMuchii = x = y = 0;
adiacenta = new vector<int>[maxi]; // Alocare memorie pentru lista de adiacenta
}
Graf::~Graf() {
delete[] adiacenta; // Eliberare memorie pentru lista de adiacenta
}
// Citirea grafului neorientat
void Graf::citireDFS() {
fin >> nrNoduri >> nrMuchii; // Citim numarul de noduri si muchii
for (int i = 1; i <= nrMuchii; i++) {
fin >> x >> y; // Citim fiecare muchie (x, y)
adiacenta[x].push_back(y); // Adaugam nodul y ca vecin al lui x
adiacenta[y].push_back(x); // Adaugam nodul x ca vecin al lui y (graful este neorientat)
}
}
// Determinarea componentelor biconexe folosind DFS
void Graf::biconex(int nodPlecare, int precedent, int k) {
vizitat[nodPlecare] = k; // Marcam nivelul curent al nodului
niv_min[nodPlecare] = k; // Initializam nivelul minim cu nivelul curent
for (auto vecin : adiacenta[nodPlecare]) { // Parcurgem toti vecinii nodului curent
if (vecin != precedent) { // Ignoram muchia care ne-a adus la acest nod (precedent)
if (!vizitat[vecin]) { // Daca vecinul nu a fost vizitat
stivaComponenteBiconexe.push({nodPlecare, vecin}); // Adaugam muchia in stiva
biconex(vecin, nodPlecare, k + 1); // Apel recursiv pentru vecinul curent
// Actualizam nivelul minim pentru nodul curent
niv_min[nodPlecare] = min(niv_min[nodPlecare], niv_min[vecin]);
// Daca vecinul nu este parte dintr-un ciclu
if (niv_min[vecin] >= vizitat[nodPlecare]) {
set<int> componenta; // Initializam componenta biconexa curenta
int aux1, aux2;
do {
aux1 = stivaComponenteBiconexe.top().first;
aux2 = stivaComponenteBiconexe.top().second;
componenta.insert(aux1); // Adaugam nodurile in componenta
componenta.insert(aux2);
stivaComponenteBiconexe.pop();
} while (aux1 != nodPlecare || aux2 != vecin); // Repetam pana terminam componenta
componenteBiconexe.push_back(componenta); // Adaugam componenta la lista finala
}
} else if (vizitat[vecin] < vizitat[nodPlecare]) { // Daca exista o muchie de intoarcere
stivaComponenteBiconexe.push({nodPlecare, vecin}); // Adaugam muchia in stiva
niv_min[nodPlecare] = min(niv_min[nodPlecare], vizitat[vecin]); // Actualizam nivelul minim
}
}
}
}
// Afisarea componentelor biconexe
void Graf::afisareComponenteBiconexe() {
fout << componenteBiconexe.size() << "\n"; // Afisam numarul de componente biconexe
for (auto &componenta : componenteBiconexe) { // Pentru fiecare componenta biconexa
for (auto nod : componenta) {
fout << nod << " "; // Afisam toate nodurile componentei
}
fout << "\n";
}
}
int main() {
Graf g1; // Cream un obiect al clasei Graf
g1.citireDFS(); // Citim graful neorientat
g1.biconex(1, 0, 1); // Determinam componentele biconexe pornind de la nodul 1
g1.afisareComponenteBiconexe(); // Afisam componentele biconexe
fin.close(); // Inchidem fisierul de intrare
fout.close(); // Inchidem fisierul de iesire
return 0;
}