Cod sursa(job #148294)

Utilizator eugen.nodeaEugen Nodea eugen.nodea Data 4 martie 2008 08:49:54
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
# include <stdio.h>
# define NMAX 100001

struct Nod{
	long v;
	Nod * ad;
  };
Nod* L[NMAX],*p,*q;
char Viz[NMAX];
long nc,N,M,i,j,x,y;
int ok;
FILE *f=fopen("dfs.in","r"),*g=fopen("dfs.out","w");

void Dfs(long k)
{
  long i;
  Nod *p;

  Viz[k]=1;
  p=L[k];
  while (p!=NULL){
	if (!Viz[(*p).v]) Dfs((*p).v);
	p=(*p).ad;
  }
}
int main()
{
  fscanf(f,"%ld %ld",&N,&M);
  for (i=1;i<=M;i++)
  {
    fscanf(f,"%ld %ld",&x,&y);
    p=new Nod;  q=L[x];
    (*p).v=y; (*p).ad=q;
    L[x]=p;
    q=new Nod; p=L[y];
    (*q).v=x; (*q).ad=p;
    L[y]=q;
  }
  fclose(f);
  nc=1; i=1;
  do{
	ok=1;
	Dfs(i);
	for (j=i;j<=N;j++)
	   if (!Viz[j])
	   {
	    ok=0; i=j;
	    nc++; break;
	   }
  }while (!ok);
  fprintf(g,"%ld",nc);
  fclose(g);
  return 0;
}