Cod sursa(job #613473)

Utilizator bocacristiBoca Nelu Cristian bocacristi Data 27 septembrie 2011 09:15:22
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#include <vector>
using namespace std;

typedef vector<int> VI;
typedef VI::iterator IT;

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

VI g[1000];
char s[1000];
int n, m;

void DFS(int nod);

int main()
{	
	int a, b;
	int nrc = 0;
	fin >> n >> m;	
	
	while ( fin >> a >> b )
	{
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for ( int i = 0; i < n; ++i )
		if ( s[i] == 0 )
		{
			nrc++;
			DFS(i);
		}		
	
	fout << nrc;
	return 0;
}

void DFS(int nod)
{
	s[nod] = 1;
	for ( IT it = g[nod].begin(); it != g[nod].end(); ++it )
		if ( s[*it] == 0 )
			DFS(*it);
}