Cod sursa(job #1431159)

Utilizator Nan_Mihai_324CCNan Mihai Nan_Mihai_324CC Data 9 mai 2015 01:02:04
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <set>
#include <queue>
#include <stack>

#define LUNG_MAX 500000

using namespace std;

typedef struct graph {
	vector<vector<pair<int, int> > > lists;
	int nrNoduri;
	int nrMuchii;
	bool *vizitat;
	int *cost_minim;
}*Graph;

Graph initGraph(int nrNoduri, int nrMuchii) {
	Graph graf = (Graph) malloc(sizeof(struct graph));
	graf->nrNoduri = nrNoduri;
	graf->nrMuchii = nrMuchii;
	graf->vizitat = (bool*) calloc(nrNoduri,sizeof(bool));
	graf->cost_minim = (int*) malloc(nrNoduri*sizeof(int));
	for(int i = 0; i < nrNoduri; i++) {
		graf->vizitat[i] = false;
		graf->cost_minim[i] = -1;
		vector<pair<int, int> > lista;
		graf->lists.push_back(lista);
	}
	return graf;
}

Graph addEdge(Graph graf, int u, int v, int cost) {
	graf->lists[u].push_back(make_pair(v, cost));
	return graf;
}

vector<pair<int, int> > getList(Graph graf, int u) {
	return graf->lists[u];
}

void dfs(Graph &graf, int source) {
	graf->vizitat[source] = true;
	for(int i = 0; i < graf->lists[source].size(); i++) {
		int v = graf->lists[source].at(i).first;
		if(graf->vizitat[v] == false) {
			dfs(graf, v);
		}
	}
}

void componente_conexe(Graph graf) {
	int nr = 0;
	for(int i = 1; i < graf->nrNoduri; i++) {
		if(graf->vizitat[i] == false) {
			dfs(graf, i);
			nr++;
		}
	}
	printf("%d\n", nr);
}

int main() {
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	int N, M, S, i, u, v;
	scanf("%d %d", &N, &M);
	Graph graf = initGraph(N+1, M);
	for(i = 0; i < M; i++) {
		scanf("%d %d", &u, &v);
		graf = addEdge(graf, u, v, 1);
	}
	componente_conexe(graf);
	return 0;
}