Pagini recente » Cod sursa (job #368135) | Cod sursa (job #2788383) | Cod sursa (job #577165) | Cod sursa (job #2096245) | Cod sursa (job #641155)
Cod sursa(job #641155)
#include <fstream>
#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]) {
out[0] = 0;
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);
ifstream f("biconex.in");
ofstream h("biconex.out");
//scanf("%ld %ld", &n, &m);
f>>n>>m;
for (i = 1; i <= m; ++i) {
//scanf("%ld %ld", &a, &b);
f>>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);
h<<cb<<"\n";
for (i = 1; i <= cb; ++i) {
long aux = show[i].size();
for (long j = 0; j < aux; ++j)
//printf("%ld ", show[i][j]);
h<<show[i][j]<<" ";
//printf("\n");
h<<"\n";
}
return 0;
}