Pagini recente » Cod sursa (job #1708963) | Cod sursa (job #728425) | Cod sursa (job #941368) | Cod sursa (job #2782944) | Cod sursa (job #641152)
Cod sursa(job #641152)
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
long n, m, a, b, i, niv[100010], niva[100010], viz[100010], cb, sk[100010], out[100010];
vector < long > g[200010], show[10000];
void df(long nod, long lev) {
long aux = g[nod].size();
niv[nod] = lev;
viz[nod] = 1;
niva[nod] = lev;
sk[++sk[0]] = nod;
for (long i = 0; i < aux; ++i) {
if (viz[g[nod][i]] == 0) {
df(g[nod][i], lev + 1);
if (niva[g[nod][i]] < niva[nod])
niva[nod] = niva[g[nod][i]];
if (niva[g[nod][i]] >= niv[nod]) {
memset(out, 0, sizeof(out));
while (sk[sk[0]] != g[nod][i]) {
out[++out[0]] = sk[sk[0]];
--sk[0];
}
--sk[0];
out[++out[0]] = g[nod][i];
out[++out[0]] = nod;
++cb;
for (long j = 1; j <= out[0]; ++j)
show[cb].push_back(out[j]);
}
} else {
if (niva[nod] > niv[g[nod][i]] && (niv[g[nod][i]] + 1 != niv[nod])) {
niva[nod] = niv[g[nod][i]];
}
}
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%ld %ld", &n, &m);
for (i = 1; i <= m; ++i) {
scanf("%ld %ld", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
for (i = 1; i <= 100010; ++i) niv[i] = 2000000000;
for (i = 1; i <= 100010; ++i) niva[i] = 2000000000;
df(1, 0);
printf("%ld\n", cb);
for (i = 1; i <= cb; ++i) {
long aux = show[i].size();
for (long j = 0; j < aux; ++j)
printf("%ld ", show[i][j]);
printf("\n");
}
return 0;
}