Pagini recente » Monitorul de evaluare | Cod sursa (job #3361657)
/*Determinare componente biconexe si puncte de articulatie*/
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define NMAX 100005
int n, m;
vector<int> G[NMAX];
int nivel[NMAX], lowest[NMAX];
vector < vector <int> > Sol;
stack<int> stiva;
void dfs(int nod, int level = 1) {
nivel[nod] = level;
lowest[nod] = level; //presupun ca nu se poate intoarce
stiva.push(nod);
for (auto vecin: G[nod]) {
if (vecin == nod) continue;
if (nivel[vecin] > 0) { //muchie de intoarcere
lowest[nod] = min(lowest[nod], nivel[vecin]);
} else {
dfs(vecin, level+1);
lowest[nod] = min(lowest[nod], lowest[vecin]);
if (lowest[vecin] >= nivel[nod]) { //vecin nu poate sari mai mult de nod -> nod articulatie
vector<int> comp;
int popped;
do {
popped = stiva.top();
comp.push_back(popped);
stiva.pop();
} while (popped != vecin);
comp.push_back(nod);
Sol.push_back(comp);
}
}
}
}
int main() {
fin >> n >> m;
for (int i = 1; i<=m; i++) {
int u,v; fin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i<=n; i++) {
if (!nivel[i]) {
dfs(i);
}
}
fout << Sol.size() << '\n';
for (auto &c: Sol) {
for (auto nod: c) {
fout << nod << ' ';
}
fout << '\n';
}
return 0;
}