Pagini recente » Cod sursa (job #674088) | Cod sursa (job #662419) | Cod sursa (job #2220108) | Cod sursa (job #2444658) | Cod sursa (job #1715709)
#include <stdio.h>
#define Nmax 200100
struct nod{
int info;
nod *next;
};
nod *p[Nmax];
nod *pt[Nmax];
int n,m,nr,viz[Nmax],postordine[Nmax],rev[Nmax],com;
void adauga(int j, int k)
{
nod *elem=new nod;
elem->info=k;
elem->next=p[j];
p[j]=elem;
}
void adaugat(int j, int k)
{
nod *elem=new nod;
elem->info=k;
elem->next=pt[j];
pt[j]=elem;
}
void DFS(int i)
{
nod *current=p[i];
viz[i]=1;
while(current!=NULL)
{
if(viz[current->info]==0)
DFS(current->info);
current=current->next;
}
postordine[++nr]=i;
}
void DFST(int i)
{
nod *current=pt[i];
viz[i]=0;
// printf("%d ",i);
adauga(n+com,i);
while(current!=NULL)
{
if(viz[current->info]!=0)
DFST(current->info);
current=current->next;
}
}
void revizit(int i)
{
nod *current=pt[i];
rev[i]=1;
while(current!=NULL)
{
if(rev[current->info]==0)
revizit(current->info);
current=current->next;
}
}
void afis(int i)
{
nod *current=p[i];
while(current)
{
printf("%d ",current->info);
current=current->next;
}
}
int main()
{
int i,x,y;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
adauga(x,y);
adaugat(y,x);
}
for(i=1;i<=n;++i)
{
if(viz[i]==0)
DFS(i);
}
for(i=n;i>0;--i)
if(viz[postordine[i]]!=0)
{
++com;
DFST(postordine[i]);
}
printf("%d\n",com);
for(i=1;i<=com;++i,printf("\n"))
for(nod *it=p[n+i];it;it=it->next)
printf("%d ",it->info);
return 0;
}