Pagini recente » Rating Baluta Iustinian-Lucian (Baluta) | Cod sursa (job #1794167) | Monitorul de evaluare | Cod sursa (job #1957555) | Cod sursa (job #1865070)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
stack <int> stv;
vector <int> ls[100005];
vector <vector <int> > sol;
bool viz[100005];
int n, m, x, y, i, ns;
int niv[100005], hmax[100005];
void write_sol(int x, int tt) {
int C;
vector <int> tmp;
tmp.push_back(tt);
//g << tmp.front() << ' ' << x << '\n';
while (!stv.empty() && (C=stv.top())!=x) {
tmp.push_back(C);
stv.pop();
}
tmp.push_back(x);
if (!stv.empty()) stv.pop();
vector <int>::iterator j;
/*for (j = tmp.begin(); j != tmp.end(); j++)
g << *j << ' ';
g << '\n';*/
sol.push_back(tmp);
}
void df(int x, int tt) {
int y, l, i;
hmax[x] = niv[x] = niv[tt]+1;
viz[x] = 1;
l = ls[x].size();
for (i = 0; i < l; i++) {
y = ls[x][i];
if (y==tt) continue;
if (viz[y] == 1) {
hmax[x] = min(hmax[x], niv[y]);
continue;
}
viz[y] = 1;
stv.push(y);
df(y, x);
hmax[x] = min(hmax[x], hmax[y]);
if (niv[x] <= hmax[y]) {
write_sol(y,x);
ns++;
}
}
}
int main() {
f >> n >> m;
while (m--) {
f >> x >> y;
ls[x].push_back(y);
ls[y].push_back(x);
}
for (i = 1; i <= n; i++)
if (viz[i] == 0) {
df(i,0);
}
vector <int>::iterator j;
vector<vector<int> >::iterator I;
g << ns << '\n';
for (I = sol.begin(); I != sol.end(); I++) {
for (j = I -> begin(); j != I -> end(); j++)
g << *j <<' ';
g << '\n';
}
return 0;
}