Pagini recente » Cod sursa (job #1387083) | Cod sursa (job #1085250) | Cod sursa (job #62714) | Cod sursa (job #716263) | Cod sursa (job #2025993)
#include <bits/stdc++.h>
using namespace std;
#define FILE_IO
typedef pair<int, int> pii;
int N, M;
int h[100005], grd[100005], low[100005];
vector<pii> edges;
vector<int> edg[100005];
bool art[100005], done[100005];
vector< vector<int> > bcc;
stack<int> stv;
int DFS(int nod, int fth)
{
h[nod] = h[fth] + 1;
low[nod] = h[nod];
stv.push(nod);
int sons = 0;
for(auto nxt: edg[nod])
{
if(nxt == fth) continue;
if(h[nxt] != 0) { low[nod] = min(low[nod], low[nxt]); continue; }
sons++;
DFS(nxt, nod);
low[nod] = min(low[nod], low[nxt]);
if(low[nxt] >= h[nod])
{
art[nod] = 1;
bcc.push_back(vector<int> ());
while(stv.top() != nod)
{
bcc.back().push_back(stv.top());
stv.pop();
}
bcc.back().push_back(nod);
}
}
//stv.pop();
return sons;
}
int main()
{
#ifdef FILE_IO
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
#endif
scanf("%d%d", &N, &M);
for(int i = 1; i <= M; i++)
{
int x, y;
scanf("%d%d", &x, &y);
edg[x].push_back(y);
edg[y].push_back(x);
}
int sns = DFS(1, 0);
if(sns > 1) art[1] = 1;
printf("%d\n", bcc.size());
for(auto v: bcc)
{
sort(begin(v), end(v));
for(auto x: v) printf("%d ", x);
printf("\n");
}
return 0;
}