Cod sursa(job #837573)

Utilizator mazaandreiAndrei Mazareanu mazaandrei Data 18 decembrie 2012 10:39:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
# include <fstream>
# include <vector>
# define Nmax 100002
using namespace std;
ifstream f("dfs.in"); ofstream g("dfs.out");vector <int> L[Nmax];
int n, m, x, y, nr , viz[Nmax];
void dfs(int p){
	viz[p]=1;
    vector <int> :: iterator it=L[p].begin(), sf=L[p].end();    
	for(; it != sf ; ++it)      
		if(!viz[*it]) dfs(*it);
}
int main(){ 
	f>>n>>m; 
	for(int i = 1; i <= m; ++i){
			f>>x>>y; L[x].push_back(y); L[y].push_back(x);
	}
	for(int i=1; i<=n; ++i )
        if(!viz[i]) {nr++; dfs(i);}
	g<<nr<<'\n';
	g.close();
	return 0;
}