Cod sursa(job #651265)

Utilizator FIIGLMFIIGherasimLupascuMiron FIIGLM Data 20 decembrie 2011 01:29:17
Problema Componente tare conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.55 kb
#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;
}