Cod sursa(job #360098)

Utilizator serbanlupulupulescu serban serbanlupu Data 29 octombrie 2009 18:59:52
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
// BFS

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int nodes;
vector< vector <int > > List;

void read(const char * buff_file)
{
	fstream f(buff_file, ios::in);
	int edges;
	f>>nodes>>edges;
	List.reserve(nodes+1);
	List.resize(nodes+1);
	
	int left, right;
	
	for (int i=1; i<=edges; ++i)
	{
		f>>left>>right;
		List[left].push_back(right);
	}
};

bool * used;
int v[1000000];
int nr_v;
int nr_com_conex;

void BFS(int node)
{
	nr_v=1;
	v[1]=node;
	used[node]=1;
	++nr_com_conex;
	
	for (int i=1; i<= nr_v; ++i)
		for (vector<int >::iterator it=List[v[i]].begin(); it != List[v[i]].end(); it++)
			if (used[*it]==0)
			{
				v[++nr_v]=*it;
				used[*it]=1;
			};
			
	for (int i=1; i<=nodes; ++i)
		if (used[i]==0)
			BFS(i);
};

void solve()
{
	used=new bool[nodes+1];
	for (int i=1; i<=nodes; ++i)
		used[i]=0;
	BFS(1);
};

void print(const char * out_file)
{
	fstream g(out_file, ios::out);
	g<<nr_com_conex;
	g.close();
}

int main()
{
	read("dfs.in");
	solve();
	print("dfs.out");
	return 0;
}