Pagini recente » Cod sursa (job #2016828) | Cod sursa (job #1574640) | Cod sursa (job #1937882)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int nmax = 100005;
int stiva[nmax], vf, nc;
bool viz[nmax];
int niv[nmax], lmax[nmax], n, i, j, x, y, m;
vector <int> ls[nmax], sol[nmax];
void pune(int x, int tt) {
int c;
sol[nc].push_back(tt);
while (vf > 0 && (c=stiva[vf]) != x) {
sol[nc].push_back(c);
vf--;
}
if (vf) {
sol[nc].push_back(x);
vf--;
}
}
void dfs(int x, int tt) {
int l = ls[x].size(), i, y;
viz[x] = 1;
lmax[x] = niv[x] = niv[tt] + 1;
for (i = 0; i < l; i++) {
y = ls[x][i];
if (y == tt) continue;
if (viz[y] == 1) {
lmax[x] = min(lmax[x],niv[y]);
continue;
}
stiva[++vf] = y;
dfs(y,x);
lmax[x] = min(lmax[x], lmax[y]);
if (niv[x] <= lmax[y]) {
nc++;
pune(y, x);
}
}
}
int main() {
f >> n >> m;
for (i = 1; i <= m; i++) {
f >> x >> y;
ls[x].push_back(y);
ls[y].push_back(x);
}
dfs(1,0);
g << nc << '\n';
for (i = 1; i <= nc; i++) {
for (j = 0; j < sol[i].size(); j++)
g << sol[i][j] << ' ';
g << '\n';
}
}