Cod sursa(job #146684)

Utilizator andrei_infoMirestean Andrei andrei_info Data 1 martie 2008 23:35:40
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream.h>

#define MAX 100005

typedef struct nnod {
			int nr;
			nnod* urm;
};

nnod* G[MAX];

char viz[MAX];
int N,M, nr_comp;

void add( int a, int b)
{
	nnod* aux = new nnod;
	aux->nr = b;
	aux->urm = G[a];
	G[a] = aux;
}

void dfs( int nod)
{
	viz[nod] = 1;
	nnod* aux = G[nod];
	while ( aux != NULL)
	{
		if (!viz[aux->nr] )
			dfs(aux->nr);
		aux = aux->urm;
	};
}

int main()
{
	ifstream fin("dfs.in");
	ofstream fout("dfs.out");

	fin>>N>>M;

	for ( ; M>0; M--)
	{
		int a,b;
		fin>>a>>b;
		add(a,b);
		add(b,a);

	}


	for (int i = 1; i<=N; i++)
		if ( !viz[i] )
		{
			nr_comp++;
			dfs(i);
		};
	fout<<nr_comp;

	return 0;
}