Cod sursa(job #1231533)

Utilizator andreioneaAndrei Onea andreionea Data 20 septembrie 2014 21:47:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>

#define IFILE "dfs.in"
#define OFILE "dfs.out"

using std::ifstream;
using std::ofstream;
using std::vector;

vector<vector<int>> vecini;
vector<bool> vizitat;

void dfs(int nod)
{
	vizitat[nod] = true;
	for (auto &i : vecini[nod])
	{
		if (!vizitat[i])
			dfs(i);
	}
}

int main()
{
	ifstream f_in(IFILE);
	ofstream fout(OFILE);
	int n, m;

	f_in >> n >> m;

	for (int i = 0; i < n; ++i)
		vecini.push_back(vector<int>());

	for (int i = 0; i < m; ++i) {
		int x,y;
		f_in >> x >> y;
		--x; --y;
		vecini[x].push_back(y);
		vecini[y].push_back(x);
	}

	f_in.close();
	for (int i = 0; i < n; ++i){
		vizitat.push_back(false);
	}
	
	int comp = 0;
	for (int i = 0; i < n; ++i) {
		if (!vizitat[i]) {
			++comp;
			dfs(i);
		}
	}

	fout << comp << "\n";
	fout.close();
	
	return 0;
}