Pagini recente » Cod sursa (job #787201) | Cod sursa (job #2638075) | Cod sursa (job #2085573) | Cod sursa (job #1863478)
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#define NMAX 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
bitset<NMAX> viz;
vector <int> ls[NMAX];
stack <int> stiva;
vector <vector <int> >sol;
int nv[NMAX], hmax[NMAX], n, i, j, x, y, m, ns;
void make_sol(int x, int tt) {
int C;
vector<int>tmp;
tmp.push_back(tt);
while (!stiva.empty() && stiva.top()!=x) {
C=stiva.top();
tmp.push_back(C);
stiva.pop();
}
tmp.push_back(x);
stiva.pop();
sol.push_back(tmp);
}
void df(int x, int tt) {
int i, l = ls[x].size(), y;
hmax[x] = nv[x] = nv[tt]+1;
viz[x]=1;
for (i = 0; i < l; i++) {
y = ls[x][i];
if (y == tt)
continue;
if (viz[y] == 0) {
stiva.push(y);
df(y,x);
hmax[x] = min(hmax[x], hmax[y]);
if (hmax[y] >= nv[x]) {
make_sol(y, x);
ns++;
}
}
else hmax[x] = min(hmax[x], nv[y]);
}
}
int main() {
f >> n >> m;
nv[0]=-1;
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 jj;
g << ns <<'\n';
for (i = 0; i < ns; i++) {
for (jj=sol[i].begin(); jj!=sol[i].end(); jj++)
g << *jj << ' ';
g << '\n';
}
return 0;
}