Pagini recente » Cod sursa (job #3181226) | Cod sursa (job #647140) | Cod sursa (job #558413) | Cod sursa (job #1329630) | Cod sursa (job #2944057)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> g[200005];
vector<int> viz(200005,0);
int n, m;
vector<int> low(200005);
vector<int> nivel(200005);
stack<int> s;// in stiva salvez elementele pe masura ce le parcurg
// in aceasta stiva se vor regasi componentele conexe sub forma de ciclu, scot din stiva pana dau de k
//mod de functionare
// creez un sir de nivel, in care salvez nivelul la care se afla fiecare nod, in dfs tree
// creez un alt sir, low, in care salvez nivelul cel mai mic accesibil din acel nod, mergand in jos(la vecinii lui care nu coincid cu tatal)
// in momentul in care dintr-un nod cu nivel x putem ajunge la un nivel mai mic decat x, atunci inseamna ca am o muchie de intoarcere
//deci am un ciclu
// componenta biconexa este un un ciclu sau o muchie (trebuie sa aiba minim 2 noduri)
// in momentul in care am doua noduri care nu se afla in acelasi componenta conexa(nu pot ajunge la acelasi nivel)
// inseamna ca am o muchie critica care leaga cele doua componente si nodul cu nivelul cel mai de sus este punctul de articulatie
//
vector<vector<int>> rez(200005);
int nr = 1;
void dfs(int k, int tata) {
viz[k] = 1;
nivel[k] = nivel[tata] + 1;
low[k] = nivel[k];
s.push(k);
for (auto i : g[k]) {
if (i != tata) {
if (viz[i] == 1) {
if (low[k] > nivel[i]) {
low[k] = nivel[i];
}
}
else {
dfs(i, k);
if (low[k] > low[i]) {// reactualizarea pe apelul de dinainte
low[k] = low[i];
}
//// punctul de articulatie leaga o muchie critica de un ciclu
//// muchiile critice sunt muchiile care leaga ciclurile
//if (nivel[k] <= low[i] && k!=1) {// punct de articulatie
////daca am ajuns intr-un punct in care am valoarea low a fiului mai mare ca nivelul tatalui
//// adica cele doua noduri nu fac parte din acelasi ciclu
////k!=1 pentru a nu lua in considerare radacina
// cout << k << ' ';
//}
//if (nivel[k] < low[i]) {// muchie critica
//// nu mai avem nivel[k] <= low[i] pentru ca nu putem avea o muchie cu o singura coordonata
// cout << k << '-' << i << '\n';
//}
//// la fel atunci cand
//// daca o componenta nu contine nici-un punct de articulatie
//// punctele de articulatie fac parte din componente biconexe
if (nivel[k] <= low[i]) {// scriere componente biconexe
while (s.top() != i) {
//cout << s.top()<<' ';
rez[nr].push_back(s.top());
s.pop();
}
//cout << i << ' ';
rez[nr].push_back(i);
s.pop();
//cout << k << '\n';
rez[nr].push_back(k);
nr++;
}
}
}
}
}
int main() {
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 0);
fout << nr-1 << '\n';
for (int i = 1; i <= nr-1; i++) {
for (auto j : rez[i]) {
fout << j << ' ';
}
fout << '\n';
}
}