Cod sursa(job #712832)

Utilizator halianStefanca Stefan halian Data 13 martie 2012 20:39:34
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <vector>
using namespace std;
#define FI fopen("dfs.in","r")
#define FO fopen("dfs.out","w")

vector<long> vecini[100001];
long n,sol;
char viz[100001];

void citeste(FILE *f) {
	long m,i,a,b;
	fscanf(f,"%li%li",&n,&m);
	for(i=0;i<m;++i) {
		fscanf(f,"%li%li",&a,&b);
		vecini[a].push_back(b);
		vecini[b].push_back(a);
	}
}

void dfs(long nod) {
	long lim=vecini[nod].size(),i;
	for(i=0;i<lim;i++) {
		if(viz[vecini[nod][i]]==0) {
			viz[vecini[nod][i]]=1;
			dfs(vecini[nod][i]);
		}
	}
}

int main() {
	long i;
	citeste(FI);
	for(i=1;i<=n;++i)
		if(viz[i]==0) {
			viz[i]=1;
			dfs(1);
			++sol;
		}
	fprintf(FO,"%li",sol);
	return 0;
}