Cod sursa(job #831954)

Utilizator un_nenorocitChelcioiu Daniel un_nenorocit Data 9 decembrie 2012 16:14:10
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
# include <stdio.h>
# include <conio.h>
# include <vector>
# define N 20000
using namespace std;

vector<int>graph[N];
int visited[N];
int n, m;

void citire () {
FILE *f = fopen ("dfs.in", "r");
int x, y;
fscanf (f, "%i %i", &n, &m);
for (int i = 0; i < n; i++){
	fscanf (f, "%i %i", &x, &y);
	graph[x].push_back(y);
	graph[y].push_back(x);
}
fclose(f);
}
void printGraph() {
	for (int i = 1; i < n; i++){
		printf("%i: ", i);
		for (int j = 0; j < graph[n].size(); j++){
			printf("%i ", graph[n].at(i));
		}
		printf("\n");
	}
}
void dfs(int start) {
	visited[start] = 1;
	for (int i =0; i < graph[start].size(); i++){
		if (visited[graph[start].at(i)] == 0)
			dfs(graph[start].at(i));
	}
}

int main () {
int nr_comp = 0;
FILE *g = fopen ("dfs.out", "w");
citire();
//printGraph();
for(int i = 1; i <= n; i++){
	if (visited[i] == 0){
		nr_comp ++;
		dfs(i);
	}
}
fprintf(g,"%i",nr_comp);
//getch();
fclose(g);
return 0;
}