Pagini recente » Cod sursa (job #1089763) | Cod sursa (job #327797) | Borderou de evaluare (job #826670) | Cod sursa (job #1010196) | Cod sursa (job #933415)
Cod sursa(job #933415)
#include <cstdio>
#include <vector>
#include <stack>
#define MAX_N 100010
using namespace std;
stack <pair <int, int> > s;
vector <int> g[MAX_N], sol[MAX_N];
int n, m, cnt, lev[MAX_N], levacc[MAX_N], u[MAX_N];
void df(int nod, int t) {
int i, v;
u[nod] = 1;
for (i = 0; i < g[nod].size(); i++) {
v = g[nod][i];
if (v == t) continue;
if (u[v]) {
levacc[nod] = min (levacc[nod], lev[v]);
continue;
}
lev[v] = levacc[v] = lev[nod] + 1;
s.push(make_pair (nod, v));
df(v, nod);
if (levacc[v] >= lev[nod]) {
cnt++;
while (1) {
sol[cnt].push_back (s.top().second);
if (s.top().first == nod) break;
s.pop();
}
sol[cnt].push_back (s.top().first);
s.pop();
}
levacc[nod] = min (levacc[nod], levacc[v]);
}
}
int main()
{
freopen ("biconex.in","r",stdin);
freopen ("biconex.out","w",stdout);
scanf ("%d %d", &n, &m);
int i, x, y;
for (i = 1; i <= m; i++) {
scanf ("%d %d", &x, &y);
g[x].push_back (y);
g[y].push_back (x);
}
df(1, 0);
printf ("%d\n", cnt);
for (i = 1; i <= cnt; i++) {
for (int j = 0; j < sol[i].size(); j++) printf ("%d ",sol[i][j]);
printf("\n");
}
return 0;
}