Pagini recente » Cod sursa (job #639160) | Cod sursa (job #708211) | Cod sursa (job #1240389) | Cod sursa (job #669470) | Cod sursa (job #383088)
Cod sursa(job #383088)
#include<fstream.h>
int low[100100],ind[100100],in,st[100100],q,start[100100],v[200100][2],nr,sol[100100],x,y,n,m,i,k,j,h[100100],cont;
int minim(int ee, int ff)
{
if(ee>ff)
return ff;
return ee;
}
void tarjan(int nod)
{
int t;
low[nod]=ind[nod]=in;
in++;
st[++q]=nod;
h[nod]=1;
t=start[nod];
while(t)
{
if(!ind[v[t][0]])
{
tarjan(v[t][0]);
low[nod]=minim(low[nod],low[v[t][0]]);
}
else
if(h[v[t][0]]&&v[t][0])
low[nod]=minim(low[nod],ind[v[t][0]]);
t=v[t][1];
}
if(low[nod]==ind[nod])
{
nr++;
do
{
h[st[q]]=0;
sol[++cont]=st[q];
q--;
}
while(sol[cont]!=nod);
sol[++cont]=0;
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
v[++k][0]=y;
v[k][1]=start[x];
start[x]=k;
}
in=1;
for(i=1;i<=n;i++)
if(!ind[i])
tarjan(i);
g<<nr<<'\n';
j=0;
for(i=1;i<=nr;i++)
{
j++;
while(sol[j])
g<<sol[j++]<<' ';
g<<'\n';
}
return 0;
}