Cod sursa(job #471596)

Utilizator bogdandudumanDuduman Bogdan Vlad bogdanduduman Data 19 iulie 2010 17:26:05
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.53 kb
#include <fstream>
#include <vector>
using namespace std;

int viz[10005],n,c,x,y,nr,j;
vector<int> a[10005];

void dfs(int d)
{
	viz[d] = 1;
	vector<int>::iterator i;
	for( i=a[d].begin(); i!=a[d].end(); i++ )
		if( viz[*i] == 0)
			dfs(*i);
}

int main()
{
	fstream f,g;
	f.open("dfs.in", ios::in);
	g.open("dfs.out", ios::out);
	
	f>>c>>n;
	for( j=1; j<=n; j++)
	{
		f>>x>>y;	// graf neorientat
		a[x].push_back(y);
		a[y].push_back(x);
	}
	
	for( j=1; j<=c; j++)
		if( viz[j] == 0)
		{
			nr++;
			dfs(j);
		}
	
	g<<nr<<"\n";
	return 0;
}