Cod sursa(job #1431155)

Utilizator Nan_Mihai_324CCNan Mihai Nan_Mihai_324CC Data 9 mai 2015 00:59:45
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

typedef struct graph {
	int nr_varfuri;
	int nr_varfuri_nevizitate;
	bool* vizitat;
	vector<vector<int> > vectori;
	int nr;
	int** matrice;
}*Graph;

Graph initGraph(int nr_varfuri) {
	Graph g;
	g = (Graph) malloc(sizeof(struct graph));
	g->nr_varfuri = nr_varfuri;
	g->nr_varfuri_nevizitate = nr_varfuri;
	g->vizitat = (bool*) calloc(nr_varfuri, sizeof(bool));
	g->matrice = (int**) malloc(nr_varfuri*sizeof(int*));
	vector<int> vect;
	for(int i = 0; i < nr_varfuri; i++) {
		g->vectori.push_back(vect);
		g->matrice[i] = (int*) malloc(nr_varfuri*sizeof(int));
		g->vizitat[i] = false;
		for(int j = 0; j < nr_varfuri; j++) {
			g->matrice[i][j] = 0;
		}
	}
	g->nr = 0;
	return g;
}

Graph addEdge(Graph g, int u, int v) {
	g->matrice[u][v] = 1;
	g->matrice[v][u] = 1;
	return g;
}

Graph readGraph() {
	int nr_varfuri, rez, x, y;
	scanf("%d", &nr_varfuri);
	Graph g = initGraph(nr_varfuri+1);
	rez = scanf("%d %d", &x, &y);
	while(rez > 0) {
		g = addEdge(g, x, y);
		rez = scanf("%d %d", &x, &y);
	}
	return g;
}

void dfs(Graph g, int src) {
	g->vizitat[src] = true;
	g->vectori[g->nr].push_back(src);
	g->nr_varfuri_nevizitate--;
	for(int i = 1; i < g->nr_varfuri; i++) {
		if(g->matrice[src][i] && !g->vizitat[i]) {
			dfs(g, i);
		}
	}
}

int main() {
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	Graph g;
	g = readGraph();
	for(int i = 1; i < g->nr_varfuri; i++) {
		if(g->nr_varfuri_nevizitate == 0) {
			break;
		}
		dfs(g, i);
		g->nr++;
	}
	printf("%d\n", g->nr);
	return 0;
}