Pagini recente » Cod sursa (job #107374) | Cod sursa (job #2459461) | Cod sursa (job #1968735) | Cod sursa (job #1061927) | Cod sursa (job #592339)
Cod sursa(job #592339)
#include <cstdio>
#include <vector>
#include <stack>
#define MAXN 100010
using namespace std;
vector <int> G[MAXN];
int dfn[MAXN], low[MAXN], n, m;
stack <pair <int, int> > stk;
vector <int> V[MAXN];
int sol, cx, cy;
void solve(int x, int y)
{
sol += 1;
V[sol].push_back(stk.top().second);
do {
cx = stk.top().first;
cy = stk.top().second;
stk.pop();
V[sol].push_back(cx);
} while(cx != x && cy != y);
}
void DF(int node, int f, int tm)
{
dfn[node] = tm;
low[node] = dfn[node];
for (vector <int> :: iterator it = G[node].begin(); it != G[node].end(); it++) {
if (*it == f) continue;
if (dfn[*it] == -1) {
stk.push(make_pair(node, *it));
DF(*it, node, tm + 1);
low[node] = min(low[node], low[*it]);
if (low[*it] >= dfn[node])
solve(node, *it); // am gasit punct de articulatie
}
else low[node] = min(low[node], dfn[*it]);
}
}
int main () {
freopen ("biconex.in", "r", stdin);
freopen ("biconex.out", "w", stdout);
int a, b, i;
scanf ("%d %d", &n, &m);
for (; m--; ) {
scanf("%d%d\n", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
for (i = 1; i <= n; i++)
dfn[i] = -1;
DF(1, 0, 0);
printf ("%d\n", sol);
for (i = 1; i <= sol; i++) {
for (int j = 0; j < V[i].size(); j++)
printf("%d ", V[i][j]);
printf ("\n");
}
return 0;
}