Pagini recente » Cod sursa (job #1340529) | Cod sursa (job #1344315) | Cod sursa (job #1730798) | Cod sursa (job #2114755) | Cod sursa (job #339448)
Cod sursa(job #339448)
#include<cstdio>
#include<vector>
int n,m,i,viz[100001],poz[100001],lvl=1,st[100001],top=0;
::std::vector<int> a[100001];
int nc;
::std::vector<int> c[100001];
int DF(int v,int niv)
{
if(viz[v])
return viz[v];
int minlvl=niv,min2,till;
viz[v] = niv;
poz[v] = lvl++;
st[++top] = v;
for(int i = 0;i < a[v].size(); ++i)
{
till = lvl;
min2 = DF(a[v][i],niv+1);
if(min2>=niv)
{
++nc;
while(poz[st[top]]>=till)
{
c[nc].push_back(st[top]);
--top;
}
if(c[nc].size())
c[nc].push_back(v);
else
--nc;
}
if(min2<minlvl)
minlvl = min2;
}
return minlvl;
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d",&n,&m);
for(int x,y;m;--m)
{
scanf("%d %d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
for(i=1;i<=n;++i)
if(!viz[i])
DF(i,1);
printf("%d\n",nc);
for(int j,i=1;i<=nc;++i)
{
for(j=0;j<c[i].size();++j)
printf("%d ",c[i][j]);
printf("\n");
}
fclose(stdout);
return 0;
}