Pagini recente » Cod sursa (job #2250451) | Cod sursa (job #1992734) | Cod sursa (job #4431) | Cod sursa (job #318030) | Cod sursa (job #423678)
Cod sursa(job #423678)
#include<stdio.h>
#include<stdlib.h>
#define FIN "ctc.in"
#define FOUT "ctc.out"
#define NMAX 100005
#define MMAX 200004
using namespace std;
struct G
{ int info;
G *next;
};
typedef G* Gr;
Gr Gn[NMAX],Gt[NMAX],REZ[NMAX],adj;
int COLOR[NMAX],n,m,x,y,nr;
void Push(Gr &q , int inf)
{
Gr p=new G;
p->info=inf;
p->next=q;
q=p;
}
void DFS(Gr graf[NMAX] , int nod , int Col , Gr &rez )
{COLOR[nod]=Col;
for ( Gr i = graf [ nod ] ; i ; i = i -> next )
if(COLOR[i->info]==Col-1)
DFS(graf,i->info,Col,rez);
Push(rez,nod);
}
int main()
{ freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{scanf("%d %d",&x,&y);
Push(Gn[x],y);
Push(Gt[y],x);
}
for(int i=1;i<=n;i++)
if(COLOR [ i ]== 0 )
{nr++;
while(adj) adj=adj->next;
DFS(Gn,i,1,adj);
DFS(Gt,i,2,REZ[nr]);
for(Gr q=adj;q;q=q->next)
if(COLOR[q->info]==1) COLOR[q->info]=0;
}
printf("%d\n",nr);
for(int i=1;i<=nr;i++)
{for(Gr q=REZ[i];q;q=q->next)
printf("%d ",q->info);
printf("\n");
}
return 0;
}