Pagini recente » Cod sursa (job #3354615) | Cod sursa (job #888301) | Cod sursa (job #3313629) | Cod sursa (job #2794055) | Cod sursa (job #3336643)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 1e5 + 5;
const char nl = '\n';
vector<int> g[NMAX], componente[NMAX];
stack<int> st;
int conexe = 0, nivel_min[NMAX], nivel[NMAX], visitat[NMAX];
void dfs(int nod, int tata, int level) {
visitat[nod] = 1;
nivel[nod] = nivel_min[nod] = level;
st.push(nod);
for (auto neigh : g[nod]) {
if (neigh == tata) continue;
if (visitat[neigh]) {
// CORECTURĂ 1: Actualizăm corect nivel_min[nod] folosind nivelul vecinului
nivel_min[nod] = min(nivel_min[nod], nivel[neigh]);
}
else {
dfs(neigh, nod, level + 1);
nivel_min[nod] = min(nivel_min[nod], nivel_min[neigh]);
// CORECTURĂ 2: Condiția pentru componente biconexe este >= (punct critic)
if (nivel_min[neigh] >= nivel[nod]) {
// Scoatem nodurile până la 'neigh' inclusiv
int curr_nod;
do {
curr_nod = st.top();
st.pop();
componente[conexe].push_back(curr_nod);
} while (curr_nod != neigh);
// CORECTURĂ 3: Nodul 'nod' (părintele) trebuie adăugat și el în componentă,
// dar NU scos din stivă, pentru că poate face parte din alte componente!
componente[conexe].push_back(nod);
conexe++;
}
}
}
}
int main() {
int n, m, x, y;
if (!(fin >> n >> m)) return 0;
for (int i = 0; i < m; i++) {
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (!visitat[i]) {
dfs(i, 0, 1);
}
}
fout << conexe << nl;
for (int i = 0; i < conexe; i++) {
for (auto nod_comp : componente[i]) {
fout << nod_comp << " ";
}
fout << nl;
}
return 0;
}