Cod sursa(job #464923)

Utilizator LuffyBanu Lavinia Luffy Data 22 iunie 2010 16:20:38
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<stdio.h>
#include<stdlib.h>
#define dim 100000
using namespace std;

int *mat[dim],n,m,i,k,nod,x,y;
char viz[dim];

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



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++)
{mat[i]=(int *)realloc(mat[i],sizeof(int));
 mat[i][0]=0;
}
	
 for(i=1;i<=m;i++)
{fscanf(f,"%d%d",&x,&y);
 //mat[x][y]=1; mat[y][x]=1;
 
 mat[x][0]++;
 mat[x]=(int *)realloc(mat[x], (mat[x][0]+1)*sizeof(int));
 mat[x][mat[x][0]]=y;
 mat[y][0]++;
 mat[y]=(int *)realloc(mat[y], (mat[y][0]+1)*sizeof(int));
 mat[y][mat[y][0]]=x;
}

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


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

fclose(f);
fclose(g);
return 0;
}