Pagini recente » Cod sursa (job #245477) | Cod sursa (job #1890026) | Cod sursa (job #2469151) | Cod sursa (job #2158970) | Cod sursa (job #1502734)
#include <stdio.h>
#include <vector>
#define MAXN 100005
#define MIN(a, b) (((a) < (b))?(a):(b))
using namespace std;
int n, m, x, y, lvl[MAXN], low[MAXN], nrBcc;
vector<int> G[MAXN], bcc[MAXN];
vector< pair<int, int> > st;
void DFS(int u, int p) {
low[u] = lvl[u] = lvl[p] + 1;
bool visp = 0;
for(auto x: G[u]) {
if(!lvl[x]) {
st.push_back(make_pair(u, x));
DFS(x, u);
low[u] = MIN(low[u], low[x]);
if(low[x] >= lvl[u]) {
++nrBcc;
pair<int, int> e;
do {
e = st.back();
st.pop_back();
bcc[nrBcc].push_back(e.second);
} while(e.first != u);
bcc[nrBcc].push_back(u);
}
}
else {
if(x != p || visp) low[u] = MIN(low[u], lvl[x]);
if(x == p) visp = 1;
}
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
while(m--) {
scanf("%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
DFS(1, 0);
printf("%d\n", nrBcc);
for(int i = 1; i <= nrBcc; i++, printf("\n"))
for(auto x: bcc[i])
printf("%d ", x);
return 0;
}