Pagini recente » Cod sursa (job #3253969) | Cod sursa (job #1381246) | Istoria paginii utilizator/mening12001 | Diferente pentru teorema-chineza-a-resturilor intre reviziile 48 si 47 | Cod sursa (job #2425503)
#include <fstream>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
vector<vector<int>> graf;
vector<int> stiva, adanc, minim;
vector<vector<int>> componente;
vector<bool> vizitat;
void DFS(int pred, int nod) {
vizitat[nod] = true;
minim[nod] = adanc[nod] = adanc[pred] + 1;
stiva.push_back(nod);
for (int vecin : graf[nod]) {
// ignoram muchia pe care am venit
if (vecin == pred) {
continue;
}
// asta e muchie de intoarcere
if (vizitat[vecin]) {
minim[nod] = min(minim[nod], adanc[vecin]);
}
// muchie de inaintare
else {
DFS(nod, vecin);
minim[nod] = min(minim[vecin], minim[nod]);
if (adanc[nod] > minim[vecin]) {
continue;
}
vector<int> comp;
// ne intoarcem pe stiva pentru a determina
// intreaga componenta biconexa
while (stiva.back() != vecin) {
comp.push_back(stiva.back());
stiva.pop_back();
}
stiva.pop_back();
comp.push_back(vecin);
comp.push_back(nod);
componente.push_back(comp);
}
}
}
int main() {
ifstream in("biconex.in");
int n;
in >> n;
graf.resize(n + 1);
vizitat.resize(n + 1);
adanc.resize(n + 1);
minim.resize(n + 1);
int m;
in >> m;
for (int i = 0; i < m; ++i) {
int start, end;
in >> start >> end;
graf[start].push_back(end);
graf[end].push_back(start);
}
DFS(0, 1);
ofstream out("biconex.out");
out << componente.size() << '\n';
for (const auto& comp : componente) {
for (int nod : comp) {
out << nod << ' ';
}
out << '\n';
}
out << '\n';
}