Cod sursa(job #1075662)

Utilizator anaid96Nasue Diana anaid96 Data 9 ianuarie 2014 13:49:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<stdio.h>
#include<stdlib.h>
#define Nmax 100001

FILE *in,*out;

int n,m,x,y;
int nrc;
int viz[Nmax];
int * A[Nmax];

void dfs(int k);
int main(void)
{
	in=fopen("dfs.in","rt");
	out=fopen("dfs.out","wt");
	fscanf(in,"%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		A[i]=(int *)realloc(A[i],sizeof(int));
		A[i][0]=0;
	}	
	for(int i=1;i<=m;i++)
	{
		fscanf(in,"%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(int i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			nrc++;
			viz[i]=nrc;
			dfs(i);
		}	
	}	
	fprintf(out,"%d",nrc);
	fclose(in);
	fclose(out);
	return 0;
}	

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