Cod sursa(job #600394)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 1 iulie 2011 16:04:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

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

int n,m,nr;
vector<int> v[1000001];
bool a[1000001];

void dfs(int & c) {
	unsigned int i;
	
	a[c]=true;
	
	for(i=0;i<(int)v[c].size();++i) if(!a[v[c][i]])
		dfs(v[c][i]);
	
}

int main() {
	
	int i,x,y;
	
	in >> n >> m;
	
	for(i=1;i<=m;++i) {
		in >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	
	for(i=1;i<=n;++i) if(!a[i]) {
		++nr;
		
		if((int)v[i].size()!=0)
			dfs(i);
	}
	out << nr << "\n";
	
	return 0;
}