Cod sursa(job #1705866)

Utilizator m.scarlat95Scarlat Marius-George m.scarlat95 Data 21 mai 2016 00:53:27
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <vector>

#define MAX	100000

unsigned int n, m, in, out;
bool visited[MAX];
std::vector< std::vector <int> > edges;

void dfs ( int root )
{
	visited[root] = true;
	for( int i = 0; i < edges[root].size(); ++i )
	{
		if( !visited[edges[root][i]] )
		{
			dfs(edges[root][i]);
		}
	}
}

int main( void )
{
	freopen( "dfs.in", "r", stdin );
	freopen( "dfs.out", "w", stdout );

	std::cin >> n >> m; 
	edges.resize(n+1);
	for( unsigned int i = 0; i < m; ++i )
	{
		std::cin >> in >> out;
		edges[in].push_back(out);
		edges[out].push_back(in);
	}

	int cnt = 0;
	int curr = 1;
	while(curr <= n)
	{
		if( !visited[curr] )
		{
			dfs(curr);
			cnt ++;
		}
	
		curr++;
	}

	std::cout << cnt << "\n";

	fclose( stdin );
	fclose( stdout );
	return 0;
}