Pagini recente » Cod sursa (job #81971) | Cod sursa (job #1335493) | Cod sursa (job #2336542) | Cod sursa (job #429444) | Cod sursa (job #2798583)
#include <iostream>
#include <list>
#include <stack>
using namespace std;
const int nMax = 100005;
list<int> a[nMax];
list<list<int>> comps;
stack<int> s;
int n, m, low[nMax];
void add(int x, int y) {
// Creeaza o noua componenta pentru afisare
list<int> comp;
// Adauga in componenta toate nodurile pana la y, inclusiv y
while (s.top() != y) {
comp.push_back(s.top());
s.pop();
}
comp.push_back(y);
s.pop();
// Adauga in componenta si pe x, separat (in caz ca e un gap in stack intre y si x)
// ^ gap-ul poate aparea daca intalnim mai multe componente biconexe ce se intorc in acelasi nod
comp.push_back(x);
comps.push_back(comp);
}
void dfs(int x, int prev, int id) {
// Initializam low-ul (nodul cel mai de sus din parcurgerea DFS in care putem ajunge)
// si punem nodul curent pe stack
low[x] = id;
s.push(x);
for (auto y: a[x]) {
// Ignoram cazul in care ne intoarcem din nodul in care am plecat
if (y == prev) continue;
// Nodul y nu a fost vizitat => viziteaza-l
if (!low[y]) {
// Viziteaza-l si actualizeaza low
dfs(y, x, id + 1);
low[x] = min(low[x], low[y]);
// Am ajuns la originea ciclului / am dat peste un nod de mai jos din parcurgerea
// DFS la care nu mai putem ajunge altfel (=> componenta biconexa)
if (low[y] >= id) {
add(x, y);
}
}
// Nodul y a fost vizitat => doar actualizeaza min-ul in caz ca e nevoie,
// fara sa risti sa afisezi o componenta biconexa de doua ori
else {
low[x] = min(low[x], low[y]);
}
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
// Input rapid
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// Initializam graful
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (!low[i]) {
dfs(i, -1, 1);
}
}
// Afisare
cout << comps.size() << "\n";
for (auto &comp: comps) {
for (auto x: comp) {
cout << x << " ";
}
cout << "\n";
}
return 0;
}