Cod sursa(job #177220)

Utilizator vladcyb1Vlad Berteanu vladcyb1 Data 12 aprilie 2008 14:24:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#include <stdlib.h>

#define NMAX 100001
#define FIN "dfs.in"
#define FOUT "dfs.out"

typedef struct nod 
{
	int info;
	struct nod * next;
} NOD;

NOD * V[NMAX];
int SEL[NMAX];
FILE * fin, * fout;
int N, M;

void push( NOD *& list, int info )
{
	NOD * q = new NOD;
	q->info = info;
	q->next = NULL;
	if( !list )
		list = q;
	else
	{
		q->next = list;
		list = q;
	}
}

void DFS( int nod )
{
	NOD * tmp;
	tmp = V[nod];
	while( tmp != NULL )
	{
		if( !SEL[tmp->info] )
		{
			SEL[tmp->info] = 1;
			DFS( tmp->info);
		}
		tmp = tmp->next;
	}
}


int main()
{
	int i, X, Y, nr = 0;
	fin = fopen( FIN, "r");
	fout = fopen( FOUT, "w" );
	fscanf( fin, "%d%d", &N, &M );
	for( i = 1; i <= N; i++ )
		V[i] = NULL;
	
	while( M )
	{
		fscanf( fin, "%d%d", &X, &Y );
		push( V[X], Y );
		push( V[Y], X );
		M--;
	}
	
	for( i = 1; i <= N; i++ )
		if( !SEL[i] )
			DFS( i ), nr++;
	
	fprintf( fout, "%d\n", nr );
	fclose( fin );
	fclose( fout );
	
}