Cod sursa(job #468814)

Utilizator cosmyoPaunel Cosmin cosmyo Data 5 iulie 2010 11:09:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<stdio.h>
#include<stdlib.h>
#define Nmax 100001
long *a[Nmax],n,m,v[Nmax],nr;
void cit()
{freopen("dfs.in","r",stdin); 
  scanf("%ld%ld",&n,&m);
   long i,x,y;
  for(i=1;i<=n;++i)
    {a[i]=(long *)realloc(a[i],sizeof(long));
     a[i][0]=0;
	}
  for(i=1;i<=m;++i)
  {scanf("%ld %ld",&x,&y);
    ++a[x][0];
   a[x]=(long *)realloc(a[x],(a[x][0]+1)*sizeof(long));
   a[x][a[x][0]]=y;
   ++a[y][0];
   a[y]=(long *)realloc(a[y],(a[y][0]+1)*sizeof(long));
   a[y][a[y][0]]=x;
  }
 fclose(stdin); 
}
void dfs(long k)
{long i;
 v[k]=1;
 for(i=1;i<=a[k][0];++i)
	 if(!v[a[k][i]])
		 dfs(a[k][i]);
}
void afis()
{long i,j;
 freopen("dfs.out","w",stdout);
  printf("%ld\n",nr);
 fclose(stdout);
}
int main()
{cit();
 long i;
  for(i=1;i<=n;++i)
	  if(!v[i])
	  {++nr;
	   dfs(i);
	  }
 afis();
 return 0;
}