Cod sursa(job #688053)

Utilizator gener.omerGener Omer gener.omer Data 22 februarie 2012 23:12:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 100005

int N, M;
vector<int> neigh[NMAX];

void read_file(){
	int a,b;
	FILE * f = fopen("dfs.in", "rt");
	fscanf(f, "%d %d", &N, &M);
	for(int i = 0; i < M; ++i){
		fscanf(f, "%d %d", &a, &b);
		neigh[a].push_back(b);
		neigh[b].push_back(a);
	}
	fclose(f);
}

vector<int> visited;

void dfs(int node){
	visited[node] = 1;
	for(unsigned i = 0; i < neigh[node].size(); ++i)
		if(!visited[neigh[node][i]])
			dfs(neigh[node][i]);
}

int nr_dfs = 0;


void dfs_1(){	
	for(int i = 1; i <= N; ++i)
		if(!visited[i]){
			++nr_dfs;
			dfs(i);
		}
}

void print_sol(){	
	FILE * f = fopen("dfs.out", "wt");
	fprintf(f, "%d ", nr_dfs);	
	fclose(f);	
}

int main(){
	read_file();
	visited.resize(N+1);
	dfs_1();
	print_sol();
	return 0;
}