Cod sursa(job #901047)

Utilizator OpportunityVlad Negura Opportunity Data 28 februarie 2013 23:49:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.55 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream fi("dfs.in");
ofstream fo("dfs.out"); 

vector <int> g[100001];
long rs,x,y,n,m,i,j,v[100001];

void read(){
	fi >> n >> m;
	for (i=1; i<=m; i++){
		fi >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
}

void dfs(long nod){
	v[nod]=1;
	for (vector <int>::iterator it=g[nod].begin(); it!=g[nod].end(); it++)
		if (!v[*it]) {v[*it]=1; dfs(*it);}
}


int main(){
	
	read();
	
	for (i=1; i<=n; i++) 
		if (!v[i]) {rs++; dfs(i);}
		
	fo << rs;
	
	return 0;
}