Pagini recente » Cod sursa (job #2201125) | Cod sursa (job #3131785) | Cod sursa (job #889144) | Cod sursa (job #1884105) | Cod sursa (job #1344419)
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
#define nmax 100010
#define mp make_pair
#define pb push_back
#define forn(i,a,b) for (int i=a;i<=b;i++)
#define forv(v,it) for (vector<int>::iterator it=v.begin();it!=v.end();it++)
int n,m,x,y,nrc;
int dfn[nmax],low[nmax];
vector<int> g[nmax],c[nmax];
stack<pair<int,int> > a;
void cbc(int x,int y)
{
int st,fi;
nrc++;
do
{
st=a.top().first;
fi=a.top().second;
c[nrc].pb(st);
c[nrc].pb(fi);
a.pop();
}while (x!=st || y!=fi);
}
void dfs(int nod,int p,int num)
{
dfn[nod]=low[nod]=++num;
forv(g[nod],it)
{
if (*it==p) continue;
if (!dfn[*it])
{
int t=*it;
a.push(mp(nod,t));
dfs(*it,nod,num);
low[nod]=min(low[nod],low[*it]);
if (low[*it]>=dfn[nod])
cbc(nod,*it);
}
else low[nod]=min(low[nod],dfn[*it]);
}
}
int main()
{
cin>>n>>m;
forn(i,1,m)
{
cin>>x>>y;
g[x].pb(y);
g[y].pb(x);
}
dfs(1,0,0);
cout<<nrc<<'\n';
forn(i,1,nrc)
{
sort(c[i].begin(),c[i].end());
c[i].erase(unique(c[i].begin(),c[i].end()),c[i].end());
forv(c[i],it)
cout<<*it<<" ";
cout<<'\n';
}
}