Cod sursa(job #591860)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 25 mai 2011 19:08:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
# include <fstream>
# include <vector>
using namespace std;

ifstream f ("dfs.in");
ofstream g ("dfs.out");

vector <int> v[100001];

int n, m, x, y, i, k, ap[100001], sol;

void make (int nod){
	ap[nod] = 1;
	int siz = v[nod].size ();
	for (int k = 0; k < siz; ++k){
		int val = v[nod][k];
		if (!ap[val])
			make (val);
	}
}
int main (){
	f >> n >> m;
	
	for (i = 1; i <= m; ++i){
		f >> x >> y;
		v[x].push_back (y);
		v[y].push_back (x);
	}
	
	for (i = 1; i <= n; ++i){
		if (!ap[i]) make (i), ++sol;
	}
	
	g << sol << '\n';
	
	g.close ();
	return 0;
}