Cod sursa(job #1007954)

Utilizator pulseOvidiu Giorgi pulse Data 9 octombrie 2013 21:59:33
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>

using namespace std;

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

const int nmax=1005;

int n,m,a[nmax][nmax],used[nmax];

void read ()
{
	fin>>n>>m;
	for (int i=1, nod1, nod2; i<=m; i++)
	{
		fin>>nod1>>nod2;
		a[nod1][nod2]=a[nod2][nod1]=1;
	}
}

void DFS (int nod)
{
	used[nod]=1;
	for (int i=1; i<=n; i++)
	{
		if (!used[i] && a[nod][i])
			DFS (i);
	}
}

int main ()
{
	read ();
	int count=0;
	for (int i=1; i<=n; i++)
	{
		if (!used[i])
		{
			count++;
			DFS (i);
		}
	}
	fout<<count;

	fin.close();fout.close();
	return 0;
}