Pagini recente » Cod sursa (job #1268952) | Cod sursa (job #42721) | Cod sursa (job #888740) | Cod sursa (job #2549636) | Cod sursa (job #2575441)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXM = 200005;
struct Edge {
int u, v;
int other (const int node) {
return u ^ v ^ node;
}
}e[MAXM];
vector<int>G[MAXN];
vector<vector<int> >bic;
bool vis[MAXN], viz[MAXN];
int h[MAXN], low[MAXN];
int stk[MAXM], top;
void dfs(int node, int papa) {
vis[node] = 1;
for (auto it:G[node]) {
int u = e[it].other(node);
if (!vis[u]) {
stk[++top] = it;
h[u] = low[u] = h[node] + 1;
dfs(u, it);
low[node] = min(low[node], low[u]);
if (low[u] >= h[node]) {
vector<int>b;
do {
int x = e[stk[top]].u;
int y = e[stk[top]].v;
top--;
if (!viz[x])
viz[x] = 1, b.push_back(x);
if (!viz[y])
viz[y] = 1, b.push_back(y);
} while (stk[top + 1] != it);
for (auto it:b)
viz[it] = 0;
bic.push_back(b);
}
} else if (it != papa) {
low[node] = min(low[node], h[u]);
}
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &e[i].u, &e[i].v);
G[e[i].u].push_back(i);
G[e[i].v].push_back(i);
}
dfs(1, 0);
printf("%d\n", bic.size());
for (auto b:bic) {
for (auto it:b)
printf("%d ", it);
printf("\n");
}
return 0;
}