Pagini recente » Cod sursa (job #2317774) | Cod sursa (job #2662632) | Cod sursa (job #2902909) | Cod sursa (job #3123602) | Cod sursa (job #1959642)
#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;
vector <int> G[MAXN], answer[MAXN];
stack < pair<int, int> > stk;
int n, m, root, biconex, depth[MAXN], low[MAXN], father[MAXN];
bool seen[MAXN];
inline void createComponent(int node1, int node2) {
biconex++;
while(stk.top().first != node1 && stk.top().second != node2) {
answer[biconex].push_back(stk.top().second);
stk.pop();
}
answer[biconex].push_back(stk.top().second);
answer[biconex].push_back(stk.top().first);
stk.pop();
}
void dfs(int node) {
seen[node] = 1;
low[node] = depth[node];
for(int son: G[node]) {
if(!seen[son]) {
depth[son] = depth[node] + 1;
father[son] = node;
stk.push({node, son});
dfs(son);
low[node] = min(low[node], low[son]);
if(low[son] >= depth[node])
createComponent(node, son);
}else if(son != father[node])
low[node] = min(low[node], depth[son]);
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int i, x, y;
scanf("%d%d", &n, &m);
for(i=1; i<=m; ++i) {
scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
depth[1] = 1;
dfs(1);
printf("%d\n", biconex);
for(i=1; i<=biconex; ++i) {
for(int node: answer[i])
printf("%d ", node);
printf("\n");
}
return 0;
}