Pagini recente » Cod sursa (job #975211) | Cod sursa (job #1662309) | Cod sursa (job #1558395) | Cod sursa (job #2164836) | Cod sursa (job #651265)
Cod sursa(job #651265)
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{ int info;
struct node *next;
} node;
node*v[100001],*p,*comp[100001];
int N,M,x,y,st[100001],L[100001],index[100001],k,level,c,viz[100001];
void TareConex(int i)
{
node *q;
k++;
index[i]=k;
L[i]=k;
level++;
st[level]=i;
viz[i]=1;
q=v[i];
while(q)
{
if(!index[q->info])
{
TareConex(q->info);
if(L[q->info]<L[i])
L[i]=L[q->info];
}
else
if(viz[q->info] && index[q->info]<L[i])
L[i]=index[q->info];
q=q->next;
}
if(L[i]==index[i])
{
++c;
while(st[level]!=i)
{
p=(node*) calloc(1,sizeof(node));
p->info=st[level];
p->next=comp[c];
comp[c]=p;
viz[st[level]]=0;
level--;
}
p=(node*) calloc( 1,sizeof(node));
p->info=i;
p->next=comp[c];
comp[c]=p;
viz[i]=0; //false;
level--;
}
}
int main()
{ int i;
node *p;
FILE *fin,*fout;
fin=fopen("ctc.in","r");
fout=fopen("ctc.out","w");
fscanf(fin,"%d%d",&N,&M);
for(i=1;i<=M;i++)
{ fscanf(fin,"%d%d",&x,&y);
if(!(p=(node*)calloc(1,sizeof(node)))) return;
p->info=y;
p->next=v[x];
v[x]=p;
}
for(i=1;i<=N;i++)
if(!index[i]) TareConex(i);
fprintf(fout,"%d\n",c);
for(i=1;i<=c;++i)
{ p=comp[i];
while(p)
{
fprintf(fout,"%d ",p->info);
p=p->next;
}
fprintf(fout,"\n");
}
fclose(fout);
fclose(fin);
return 0;
}