Pagini recente » Cod sursa (job #1884347) | Cod sursa (job #62216) | Cod sursa (job #2336502) | Cod sursa (job #1514987) | Cod sursa (job #2026005)
#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];
pii edges[200005];
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];
int sons = 0;
for(auto e: edg[nod])
{
int nxt = nod ^ edges[e].first ^ edges[e].second;
if(nxt == fth) continue;
if(h[nxt] != 0) { low[nod] = min(low[nod], h[nxt]); continue; }
stv.push(e);
sons++;
DFS(nxt, nod);
low[nod] = min(low[nod], low[nxt]);
if(low[nxt] >= h[nod])
{
art[nod] = 1;
bcc.push_back(vector<int> ());
int ee = stv.top();
do
{
ee = stv.top();
bcc.back().push_back(edges[ee].first);
bcc.back().push_back(edges[ee].second);
stv.pop();
}while(ee != e);
}
}
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(i);
edg[y].push_back(i);
edges[i] = {x, y};
}
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));
v.erase(unique(v.begin(), v.end()), v.end());
for(auto x: v) printf("%d ", x);
printf("\n");
}
return 0;
}