Cod sursa(job #795717)

Utilizator Coman95coman cosmin Coman95 Data 9 octombrie 2012 15:18:51
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>
#include <vector>
using namespace std;

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

#define INF 0x3f3f3f3f
typedef vector<int> VI;

VI g[101];
int nr, n;
bool s[101];
void DFS( int x );

int main()
{
	int x, y;
	while( fin >> x >> y )
	{
		g[x].push_back( y );
		g[y].push_back( x );
		n++;
	}
	for( int i = 1; i <= n; ++i )
		if( !s[i] )
		{
			DFS( i );
			nr++;
		}
	fout << nr << '\n';
	fin.close();
	fout.close();
	return 0;
}

void DFS( int x )
{
	s[x] = true;
	for( size_t i = 1; i <= g[x].size(); ++i )
		if( !s[i] )
			DFS( i );
}