Pagini recente » Cod sursa (job #1576329) | Cod sursa (job #2812667) | Cod sursa (job #2841908) | Cod sursa (job #2817721) | Cod sursa (job #3194575)
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
ifstream in("biconex.in");
ofstream out("biconex.out");
#define cin in
#define cout out
#endif // LOCAL
const int nmax = 1e5 + 7;
vector<int> g[nmax];
int depth[nmax], low[nmax];
int ap[nmax];
stack<int> dfs_stack; // retine nodurile pe care le-am vizitat in DFS in
// ordinea in care le-am vizitat pentru a ajunge la nodul curent
// !! nu retine toate nodurile vizitate, ci doar cele de pe un anumit lant
// de la radacina pana la nodul curent
vector<vector<int>> comp_biconexe;
void dfs(int node, int parent, int adancime) {
// cerr << "Called DFS with " << node << " " << parent << " " << adancime << "\n";
// Adaugam nodul curent in stiva
dfs_stack.push(node);
depth[node] = low[node] = adancime;
bool este_punct_de_articulatie = false;
int nr_fii = 0;
for(auto vec : g[node]) {
if (vec == parent)
continue; // cazul cand m-as intoarce la parinte dar nu am muchie de "back" catre parinte
if (depth[vec] == -1) { // cazul cand merg intr-un nod nevizitat, deci imi este fiu si are muchie verde
++nr_fii;
dfs(vec, node, adancime + 1);
low[node] = min(low[node], low[vec]);
if (low[vec] >= depth[node]) {
este_punct_de_articulatie = true;
// Pe langa faptul ca ap[node] = true, mai stim si ca
// de la fiul vec in jos avem o componenta biconexa separata
// pe care o putem extrage folosind informatia din stack
vector<int> comp_curent;
while(dfs_stack.top() != vec) {
comp_curent.push_back(dfs_stack.top());
dfs_stack.pop();
}
comp_curent.push_back(dfs_stack.top());
dfs_stack.pop();
comp_curent.push_back(node); // il adaug "din burta" fiindca node, fiind punct de articulatie,
// poate aparea si in alte componente biconexe
// deci nu il pot scoate din stack
comp_biconexe.push_back(comp_curent);
}
} else { // cazul cand merg intr-un nod vizitat, deci imi este parinte si are muchie rosie
low[node] = min(low[node], depth[vec]);
}
}
// cerr << node << " " << depth[node] << " " << low[node] << "\n";
// cerr << "nr_fii = " << nr_fii << "\n";
// cerr << "este_punct_de_articulatie = " << este_punct_de_articulatie << "\n";
// Un nod este punct de articulatie daca are un fiu vec astfel incat low[vec] >= depth[node]
if ( adancime > 0 /* nu suntem in radacina */ && este_punct_de_articulatie )
ap[node] = true;
// Si mai avem caz special pentru radacina
if ( adancime == 0 && nr_fii >= 2 )
ap[node] = true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
for(int i = 0; i < nmax; i++) {
depth[i] = -1;
low[i] = -1;
}
int n, m; cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 1, 0);
// Afisam punctele de articulatie
#ifdef LOCAL
for(int i = 1; i <= n; i++) {
if(ap[i] == true) {
cerr << i << " este punct de articulatie\n";
}
}
#endif // LOCAL
// Afisam componentele biconexe
cout << comp_biconexe.size() << "\n";
for(auto comp : comp_biconexe) {
for(auto nod : comp) {
cout << nod << " ";
}
cout << "\n";
}
}