Cod sursa(job #591856)

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

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

vector <int> v[100001];
queue <int> Q;


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

void make (int nod){
	ap[nod] = 1;
	Q.push (nod);
	
	for (; !Q.empty (); Q.pop ()){
		int val = Q.front ();
		int siz = v[val].size ();
		for (k = 0; k < siz; ++k){
			if (!ap[v[val][k]]){
				Q.push (v[val][k]);
				ap[v[val][k]] = 1;
			}
		}
	}
	
	++sol;
}
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);
	}
	
	g << sol << '\n';
	
	g.close ();
	return 0;
}