Pagini recente » Cod sursa (job #544605) | Cod sursa (job #286419) | Cod sursa (job #3222409) | Cod sursa (job #2693329) | Cod sursa (job #3196382)
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
ifstream in("biconex.in");
ofstream out("biconex.out");
#define cin in
#define cout out
#endif
const int nmax = 1e5 + 7;
vector<int> g[nmax]; // graful nostru
int depth[nmax]; // adancimea nodului i
int viz[nmax]; // vizitat sau nu
int low[nmax]; // low[i] = cea mai mica adancime la care putem ajunge pornind din i in arborele dfs,
// dat fiind ca avem voie sa folosim o muchie "verde" (de intoarcere) o singura data
int ancestor[nmax]; // tatal direct al nodului i in arborele dfs
void dfs(int nod, int tata, int adancime) {
depth[nod] = adancime;
ancestor[nod] = tata;
viz[nod] = 1;
for (auto vecin : g[nod]) {
if (vecin == tata || viz[vecin]) continue;
dfs(vecin, nod, adancime + 1);
}
return;
}
void dfs_low(int nod, int tata) {
low[nod] = depth[nod];
for(auto vecin : g[nod]) {
if(vecin == tata || depth[vecin] > depth[nod]) continue;
// am gasit o muchie de intoarcere!
// cerr << "Intoarcere: " << nod << " " << vecin << "\n";
low[nod] = min(low[nod], depth[vecin]);
}
// altfel presupunem ca incercam o muchie "rosie" catre un fiu
for(auto vecin : g[nod]) {
if(vecin == tata || depth[vecin] != depth[nod] + 1) continue;
// incercam o muchie "rosie" catre fiu
dfs_low(vecin, nod);
// acum stim low[vecin] pentru ca am apelat dfs_low pe vecin
// deci putem updata low[nod] cu low[vecin]
low[nod] = min(low[nod], low[vecin]);
}
return;
}
vector<int> puncte_critice;
void dfs_critice(int node, int tata) {
bool este_critic = false;
int nr_fii = 0;
for(auto vec : g[node]) {
if(vec == tata) continue;
if(depth[vec] != depth[node] + 1) continue;
++nr_fii;
if(low[vec] >= depth[node]) {
este_critic = true;
}
dfs_critice(vec, node);
}
// si avem 2 cazuri, fiindca radacina este punct critic daca are mai mult de 1 fiu
// si chiar daca este_critic == false pentru radacina
if(tata == 0 /* suntem in radacina */ && nr_fii >= 2) {
este_critic = true;
}
if(este_critic) {
puncte_critice.push_back(node);
}
}
vector<pair<int, int>> poduri;
void dfs_poduri(int node, int tata) {
for(auto vec : g[node]) {
if(vec == tata) continue;
if(depth[vec] != depth[node] + 1) continue;
if(low[vec] > depth[node]) {
poduri.push_back({node, vec});
}
dfs_poduri(vec, node);
}
}
vector<vector<int>> biconexe_pe_noduri;
stack<int> dfs_stack;
void dfs_biconexe(int node, int tata) {
dfs_stack.push(node);
for(auto vec : g[node]) {
if(vec == tata) continue;
if(depth[vec] != depth[node] + 1) continue;
dfs_biconexe(vec, node);
if(low[vec] >= depth[node]) {
// am gasit o componenta biconexa
vector<int> comp_biconexa;
while(dfs_stack.top() != vec) {
comp_biconexa.push_back(dfs_stack.top());
dfs_stack.pop();
}
comp_biconexa.push_back(vec);
comp_biconexa.push_back(node);
dfs_stack.pop();
biconexe_pe_noduri.push_back(comp_biconexa);
}
}
}
int main() {
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, 0, 1);
#ifdef LOCAL
cerr << "Depth: " << "\n";
for (int i = 1; i <= n; ++i) {
cerr << depth[i] << " ";
}
cerr << "\n";
#endif
dfs_low(1, 0);
// Eu vreau sa ma uit care noduri au low[i] == depth[i]
#ifdef LOCAL
cerr << "Low: " << "\n";
for (int i = 1; i <= n; ++i) {
cerr << low[i] << " ";
}
cerr << "\n";
#endif
// Ce inseamna ca un nod sa aiba low[i] == depth[i]?
// 1. Nu face parte dintr-un ciclu sau este fix tatal unui ciclu
// Hai sa aflam punctele critice / de articulare!
dfs_critice(1, 0);
#ifdef LOCAL
cerr << "Punctele critice sunt: ";
for (auto nod : puncte_critice) {
cerr << nod << " ";
}
cerr << "\n";
#endif
// Hai sa gasim poduri!
// Un pod este un nod intre 2 puncte critice
// Dar mai mult de atat, muchia trebuie sa fie "rosie" de la tata la fiu
// Trebuie si ca fiul sa nu aiba low mai mic sau egal decat depth-ul tatalui
dfs_poduri(1, 0);
#ifdef LOCAL
cerr << "Podurile sunt: " << endl;
for (auto pod : poduri) {
cerr << pod.first << " " << pod.second << "\n";
}
cerr << "\n";
#endif
// Hai sa gasim biconexe!
dfs_biconexe(1, 0);
cout << biconexe_pe_noduri.size() << endl;
for(auto comp_biconexa : biconexe_pe_noduri) {
for(auto nod : comp_biconexa) {
cout << nod << " ";
}
cout << "\n";
}
}