Cod sursa(job #466285)

Utilizator bugyBogdan Vlad bugy Data 26 iunie 2010 12:48:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<stdio.h>
#include<stdlib.h>
#define dim 100005
using namespace std;

short int viz[dim];
int n,m,i,*A[dim],x,y,cc;


void DFS(int nod);

int main()
{	 FILE *f=fopen("dfs.in","r"), *g=fopen("dfs.out","w");
 
fscanf(f,"%d%d",&n,&m);

for(i=1;i<=n;i++)
	{
	A[i]=(int *)realloc(A[i],sizeof(int));
	A[i][0]=0;
	}
	
 for(i=1;i<=m;i++)
{
	fscanf(f,"%d%d",&x,&y);
 A[x][0]++;
 A[x]=(int *)realloc(A[x], (A[x][0]+1)*sizeof(int));
 A[x][A[x][0]]=y;
 
 A[y][0]++;
 A[y]=(int *)realloc(A[y], (A[y][0]+1)*sizeof(int));
 A[y][A[y][0]]=x;
}

for(i=1;i<=n;i++)
	if(!viz[i])
	{cc++; DFS(i);}

fprintf(g,"%d\n",cc);

fclose(f);
fclose(g);

return 0;
}

void DFS(int nod)
{int i;
viz[nod]=1;
 for(i=1;i<=A[nod][0];i++)
  if(!viz[ A[nod][i] ])
	DFS(A[nod][i]);	
}