Pagini recente » Cod sursa (job #1111466) | Cod sursa (job #3211273) | Cod sursa (job #878178) | Cod sursa (job #280856) | Cod sursa (job #2815817)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("biconex.in");
ofstream out ("biconex.out");
const int N = 100001;
const int M = 200001;
int n,m, urm[M*2], lst[N], vf[2*M],nr,nivel[N],niv_min[N],stk[N],k,nbc;
vector <int> cmp_b [N];
void adauga (int x, int y) {
vf[++nr]=y;
urm[nr]=lst[x];
lst[x]=nr;
}
void dfs (int x, int parent) {
niv_min[x] = nivel[x];
stk[++k] = x;
for (int p = lst[x]; p != 0; p = urm[p]) {
int y = vf[p];
if (y == parent) continue;
if (!nivel[y] ) {
nivel[y] = nivel[x] + 1;
dfs(y,x);
if (niv_min[y] >= nivel[x]) {
nbc++;
while (k && stk[k] != y) {
cmp_b[nbc].push_back(stk[k--]);
}
cmp_b[nbc].push_back(stk[k--]);
cmp_b[nbc].push_back(x);
}
niv_min[x] = min(niv_min[x], niv_min[y]);
}
else {
niv_min[x] = min(niv_min[x], nivel[y]);
}
}
}
int main() {
in>>n>>m;
int x,y;
for (int i=0;i<m;i++) {
in>>x>>y;
adauga(x,y);
adauga(y,x);
}
for (int i=1;i<=n;i++) {
if (!nivel[i])
dfs(i,0);
}
out<<nbc<<'\n';
for (int i = 1; i <= nbc; i++) {
for (int j = 0; j < cmp_b[i].size(); j++) {
out<<cmp_b[i][j]<<' ';
}
out<<'\n';
}
return 0;
}