Pagini recente » Cod sursa (job #2819780) | Cod sursa (job #713267) | Cod sursa (job #2754572) | Profil Latif371 | Cod sursa (job #1563595)
#include <iostream>
#include <cstdio>
#include <vector>
#define MAXN 100050
using namespace std;
vector<int> graf[MAXN];
vector<vector<int> > sol;
vector<pair<int, int> > stiva;
int n, m;
int depth[MAXN], low[MAXN], viz[MAXN];
void citire()
{
int x, y;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d %d", &x, &y);
graf[x].push_back(y);
graf[y].push_back(x);
}
}
void updateSolution(int nod, int y)
{
int cx, cy;
vector<int> newSol;
while (!stiva.empty()) {
cx = stiva.back().first;
cy = stiva.back().second;
stiva.pop_back();
newSol.push_back(cy);
if (nod == cx && y == cy)
break;
}
newSol.push_back(nod);
sol.push_back(newSol);
}
void dfs(int nod, int d)
{
int eArticulatie = 0;
viz[nod] = 1;
depth[nod] = d;
low[nod] = d;
for (int i = 0, t = graf[nod].size(); i < t; i++) {
int y = graf[nod][i];
if (!viz[y]) {
stiva.push_back(make_pair(nod, y));
dfs(y, d+1);
low[nod] = min(low[nod], low[y]);
if (depth[nod] <= low[y]) {
eArticulatie = 1; /// doar daca nod-ul nu-i root dar nu ne intereseaza
updateSolution(nod, y);
}
}
else
low[nod] = min(low[nod], depth[y]);
}
}
void afisare()
{
printf("%d\n", sol.size());
for (int i = 0, t = sol.size(); i < t; i++, printf("\n"))
for (int j = 0, s = sol[i].size(); j < s; j++)
printf("%d ", sol[i][j]);
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
citire();
dfs(1, 0);
afisare();
return 0;
}