Cod sursa(job #360102)

Utilizator serbanlupulupulescu serban serbanlupu Data 29 octombrie 2009 19:22:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 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);
	int edges;
	f>>nodes>>edges;
	List.reserve(nodes+1);
	List.resize(nodes+1);
	int left, right;
	for (int i=1; i<=edges; ++i)
	{
		f>>right>>left;
		List[right].push_back(left);
		List[left].push_back(right);
	}
	f.close();
};

bool used[200000];

int nr_conex;

void dfs(int i)
{
	for (vector<int>::iterator it=List[i].begin(); it < List[i].end(); it++)
		if (used[*it] == 0)
		{
			used[*it]=1;
			dfs(*it);
		}
};

void solve()
{
	used[1]=1;
	nr_conex=1;
	dfs(1);
	for (int i=1; i<=nodes; ++i)
		if (used[i]==0)
		{
			++nr_conex;
			used[i]=1;
			dfs(i);
		}
	fstream g("dfs.out", ios::out);
	g<<nr_conex;
	g.close();
}

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