Cod sursa(job #393924)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 10 februarie 2010 10:39:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <fstream>
#include <vector>

using namespace std;

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

vector<int>a[1<<17];
int n;
bool viz[1<<17]={false};

void citire(){
	int x,y,m;
	in>>n>>m;
	while(m--){
		in>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
}

void dfs(int x){
	int i,y;
	viz[x]=true;
	for(i=0;i<a[x].size();i++){
		y=a[x][i];
		if(viz[y])
			continue;
		dfs(y);
	}
}
	

int main(){
	int i,nr=0;
	citire();
	for(i=1;i<=n;i++){
		if(!viz[i]){
			nr++;
			dfs(i);
		}
	}
	out<<nr;
	return 0;
}