Pagini recente » Cod sursa (job #1180389) | Cod sursa (job #2918047) | Cod sursa (job #583507) | Cod sursa (job #1128797) | Cod sursa (job #2077770)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
vector <int> graf[100100],sol[100100];
int st[100001],vf,n,m,level[100001],hang[100001],l[100001],nr;
void read ()
{ int x,y;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
graf[x].push_back(y); l[x]++;
graf[y].push_back(x); l[y]++;
}
}
void dfs ()
{
vf=1; hang[1]=1;
st[vf]=1; level[1]=1;
while(vf)
{
int nod=st[vf],fiu,ok=0;
while(l[nod]>0)
{
l[nod]--; fiu=graf[nod][l[nod]];
if(level[fiu]!=0) hang[nod]=min(hang[nod],level[fiu]);
else {st[++vf]=fiu,hang[fiu]=level[nod],level[fiu]=level[nod]+1;ok=1;break;}
}
if(ok==0)
{
if(hang[st[vf]]>=level[st[vf-1]] && vf!=1)
{ ++nr; sol[nr].push_back(st[vf-1]);
for(int u=vf;st[u]!=0;u++)
sol[nr].push_back(st[u]),st[u]=0;
vf--;
} else vf--,hang[st[vf]]=min(hang[st[vf]],hang[st[vf+1]]);
}
}
}
void write ()
{
cout<<nr<<"\n";
for(int i=1;i<=nr;++i)
{
for(int j=0;j<sol[i].size();j++)
cout<<sol[i][j]<<" ";
cout<<"\n";
}
}
int main()
{
read();
dfs();
write();
cin.close();
cout.close();
return 0;
}