Cod sursa(job #413559)

Utilizator nandoLicker Nandor nando Data 8 martie 2010 19:05:25
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <cstdio>
#include <vector>

using namespace std;

FILE* fin=fopen("dfs.in","r");
FILE* fout=fopen("dfs.out","w");
#define NOD_MAX 100005

vector<int> nod[NOD_MAX];
bool viz[NOD_MAX];
int n,m;

void dfs(int i){
	viz[i]=true;
	for(int j=0;j<nod[i].size();j++){
		dfs(nod[i][j]);
	}
}
int main(){
	fscanf(fin,"%u %u",&n,&m);
	int x,y,con=0;
	for(int i=0;i<m;i++){
		fscanf(fin,"%u %u",&x,&y);
		nod[x].push_back(y);
	}
	for(int i=1;i<=n;i++){
		if(!viz[i]){
			dfs(i),con++;
		}
	}
	fprintf(fout,"%u\n",con);
	fclose(fin);
	fclose(fout);
	return 0;
}