Pagini recente » Cod sursa (job #2884958) | Cod sursa (job #488890) | Cod sursa (job #1724699) | Cod sursa (job #2354860) | Cod sursa (job #3194584)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100002;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int depth[NMAX], low[NMAX];
vector < vector < int > > v, biconexe;
stack < int > s; ///nodurile vizitate in dfs IN ORDINE
void dfs(int nod, int parent, int adancime) {
s.push(nod);
depth[nod] = low[nod] = adancime;
for(auto var : v[nod]) {
if(var == parent) ///n-are cum sa fie muchie de back
continue;
if(depth[var] == -1) { ///nod nevizitat
dfs(var, nod, adancime + 1);
low[nod] = min(low[nod], low[var]);
if(low[var] >= depth[nod]) {
vector < int > comp; ///salvam in comp componenetele bicon, care sunt deja in stiva
while(s.top() != var) {
comp.push_back(s.top());
s.pop();
}
comp.push_back(s.top());
s.pop();
comp.push_back(nod);
biconexe.push_back(comp);
}
}
else
low[nod] = min(low[nod], depth[var]);
}
}
void init(int n) {
for(int i = 0; i <= n; i++) {
depth[i] = -1;
low[i] = -1;
}
}
int main()
{
int n, m, a, b;
cin >> n >> m;
init(n);
v.resize(n + 1);
for(int i = 1; i <= m; i++) {
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1, 1, 0);
cout << biconexe.size() << '\n';
for(int i = 0; i < biconexe.size(); i++) {
for(int j = 0; j < biconexe[i].size(); j++)
cout << biconexe[i][j] << " ";
cout << '\n';
}
return 0;
}