Cod sursa(job #360099)

Utilizator serbanlupulupulescu serban serbanlupu Data 29 octombrie 2009 19:09:31
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
// DFS

#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);
	f>>nodes;
	int edges;
	f>>edges;
	int left, right;
	List.reserve(nodes+1);
	List.resize(nodes+1);
	
	for (int i=1; i<=nodes; ++i)
	{
		f>>left>>right;
		List[left].push_back(right);
		List[right].push_back(left);
	}
	f.close();
};

bool * used;
int v[100001];
int nr_v;
int nr_conex;

void BFS(int node)
{
	++nr_conex;
	nr_v=1;
	v[1]=node;
	used[node]=1;
	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];
	BFS(1);
};

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

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