Pagini recente » Cod sursa (job #3197734) | Cod sursa (job #234654) | Cod sursa (job #2115999) | Cod sursa (job #2626127) | Cod sursa (job #496603)
Cod sursa(job #496603)
#include <stdio.h>
const int maxn=100001;
struct nod {
int inf;
nod *next;
} *A[maxn],*Sol[maxn];
int i,N,M, ind[maxn],inS[maxn],lowlink[maxn],st[2*maxn],NR,k,index;
void citire()
{
int x,y;
scanf("%d %d",&N,&M);
for(i=1;i<=M;i++)
{
scanf("%d %d",&x,&y);
nod *q=new nod;
q->inf=y;
q->next=A[x];
A[x]=q;
}
}
int min(int a, int b)
{
if(a<b) return a;
return b;
}
void tarjan(int p)
{
ind[p]=index;
lowlink[p]=index;
index++;
st[++k]=p; inS[p]=1;
for(nod *x=A[p];x;x=x->next)
{
if(ind[x->inf]==0)
{
tarjan(x->inf);
lowlink[p]=min(lowlink[p],lowlink[x->inf]);
}
else
if(inS[x->inf])
lowlink[p]=min(lowlink[p],ind[x->inf]);
}
if(lowlink[p] == ind[p])
{
NR++;
do
{
nod *s=new nod;
s->inf=st[k];
s->next=Sol[NR];
Sol[NR]=s;
inS[st[k]]=0;
}
while(st[k--]!=p);
}
}
void afisare()
{
printf("%d\n",NR);
for(i=1;i<=NR;i++)
{
for(nod *x=Sol[i];x;x=x->next)
printf("%d ",x->inf);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
citire();
index=1;
for(i=1;i<=N;i++)
if(ind[i]==0) tarjan(i);
afisare();
}