Pagini recente » Cod sursa (job #2801792) | Autentificare | Cod sursa (job #1760241) | Cod sursa (job #1760257) | Cod sursa (job #2799757)
#include <cassert>
#include <cstdio>
#include <vector>
#include <stack>
#define MAXN 100000
#define MIN(a, b) ((a) < (b) ? (a) : (b))
std::vector<int> edges[MAXN];
bool viz[MAXN];
int nivel[MAXN];
int low[MAXN];
std::stack<int> stack;
std::vector<int> ret[MAXN];
size_t k = 0;
void
dfs (int nod, int parent = -1) {
viz[nod] = true;
low[nod] = nivel[nod];
stack.emplace(nod);
for (auto to: edges[nod]) {
if (to == parent)
continue;
if (viz[to]) {
low[nod] = MIN(low[nod], nivel[to]);
continue;
}
nivel[to] = nivel[nod] + 1;
dfs(to, nod);
low[nod] = MIN(low[nod], low[to]);
if (nivel[nod] < low[to]) {
/* Muchie critică de la nod la to */
}
if (nivel[nod] == low[nod]) {
/* Nod critic */
}
if (nivel[nod] == low[nod] || nivel[nod] <= low[to]) {
int last;
do {
last = stack.top();
stack.pop();
ret[k].emplace_back(last);
} while (last != to);
ret[k].emplace_back(nod);
++ k;
}
}
}
int main () {
int n, m;
int i;
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d%d", &n, &m);
for (i = 0; i != m; ++ i) {
int de, la;
scanf("%d%d", &de, &la);
-- de, -- la;
edges[de].emplace_back(la);
edges[la].emplace_back(de);
}
dfs(0);
printf("%zu\n", k);
for (i = 0; i != k; ++ i) {
for (auto val: ret[i])
printf("%d ", val + 1);
putchar('\n');
}
}