Cod sursa(job #795727)

Utilizator Coman95coman cosmin Coman95 Data 9 octombrie 2012 15:24:44
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;

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

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

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

int main()
{
	fin >> n >> m;
	int x, y;
	while( fin >> x >> y )
	{
		g[x].push_back( y );
		g[y].push_back( x );
	}
	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 = 0; i < g[x].size(); ++i )
		if( !s[g[x][i]] )
			DFS( g[x][i] );
}