Cod sursa(job #1410436)

Utilizator OrolesVultur Oroles Data 31 martie 2015 01:56:53
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>

class Node
{
public:
	std::vector<int> neighbour;
};

std::vector<Node> nodes(100000);
std::vector<bool> visited(100000);

void dfs( int start )
{
	std::list<int> queue;
	queue.push_back( start );
	while( !queue.empty() )
	{
		int head = queue.front();
		queue.pop_front();
		visited[head] = true;
		for ( int i = 0; i < nodes[head].neighbour.size(); ++i )
		{
			if ( visited[nodes[head].neighbour[i]] == false )
			{
				queue.push_back( nodes[head].neighbour[i] );
			}
		}
	}
}

int main( int argc, char* argv[] )
{
	std::ifstream input( "dfs.in" );
	std::ofstream output( "dfs.out" );

	int N,M;
	input >> N >> M;
	for ( int i = 0; i < M; ++i )
	{
		int first, second;
		input >> first >> second;
		nodes[first].neighbour.push_back(second);
	}
	
	int contor = 0;
	for ( int i = 1; i <= N; ++i )
	{
		if ( visited[i] == false )
		{
			dfs(i);
			contor++;
		}
	}

	output << contor;

	input.close();
	output.close();
	return 0;
}