Cod sursa(job #1431626)

Utilizator Dobre_Andrei_Ciprian_325CBDobre Andrei Ciprian Dobre_Andrei_Ciprian_325CB Data 9 mai 2015 11:04:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.72 kb
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <list>
#include <vector>
#include <queue>
#include <fstream>
#include <string>
#include <algorithm>
#include <map>
#define MAX_N 100000
#define INF 20000

using namespace std;
typedef struct vertex{
		int p;
		char colour;
		int content;
		int dist;
}Vertex;

typedef struct graph{
	std::vector< std::list<int> >adjacency_list;
	std::vector<vertex> nodes;
	int N, M, C;
	int degrees[MAX_N];
}Graph;

void reset_colours(Graph *G){
	int i;
	for(i = 0; i < G->N; i++)
		G->nodes[i].colour = 'w';
}

void read_input(const char* file_name, Graph* G){
	std::ifstream file_stream(file_name);
	file_stream >> G->N >> G->M;
	int i, aux1, aux2, cost;
	for(i = 0; i < G->N; i++) {
		Vertex new_node;
		new_node.p = -1;
		new_node.colour = 'w';
		new_node.content = i;
		new_node.dist = INF;
		G->nodes.push_back(new_node);
		G->degrees[i] = 0;
		std::list<int> l;
		G->adjacency_list.push_back(l);
	}
	while(file_stream >> aux1 >> aux2){
		G->adjacency_list[aux1 - 1].push_back(aux2 - 1);
		G->adjacency_list[aux2 - 1].push_back(aux1 - 1);
		// G->degrees[aux2 - 1]++;
		// G->edges.insert(make_pair(make_pair(aux1, aux2), cost));		
	}
	file_stream.close();
}

void display_structure(Graph *G){
	int i;
	printf("Nodes: [%i]\n", G->N);
	for(i = 0; i < G->N; i++){
		std::list<int>::iterator it;
		printf("Node %i -> (", i);
		for(it = G->adjacency_list[i].begin(); it != G->adjacency_list[i].end(); it++){
			printf("%i,", *it);
		}
		if(G->adjacency_list[i].size() > 0)printf("\b)\n");
		// else printf(")[%i]\n", int(adjacency_list[i].size()));
		else printf(")\n");
	}
	// if(G->edges.size() > 0){
	// 	printf("Edges: \n");
	// 	std::map< std::pair<int, int>, int >::iterator mit;
	// 	for(mit = G->edges.begin(); mit != G->edges.end(); mit++){
	// 		printf("(%i,%i) -> %i\n", mit->first.first, mit->first.second, mit->second);
	// 	}
	// }
}

void explore(int node, Graph* G){
	G->nodes[node].colour = 'g';
	std::list<int>::iterator it;
	for(it = G->adjacency_list[node].begin(); it != G->adjacency_list[node].end(); it++)
		if(G->nodes[*it].colour == 'w'){
			G->nodes[*it].p = node;
			G->nodes[*it].dist = G->nodes[node].dist + 1;
			explore(*it, G);
		}
	G->nodes[node].colour = 'b';
	// printf("%i[%i] ", node, G->nodes[node].dist);
	// printf("%i ", node);
}

long dfs_list(Graph* G){
	long count = 0;
	reset_colours(G);
	long i;
	for(i = 0; i < G->N; i++)
		if(G->nodes[i].colour == 'w'){
			G->nodes[i].dist = 0;
			// printf("\n");
			count++;
			explore(i, G);
		}
	return count;
}

int main(){
	// cout << "Hello World!";
	Graph G;
	read_input("dfs.in", &G);
	ofstream out("dfs.out");
	// display_structure(&G);
	long i = dfs_list(&G);
	// cout << i << endl;
	out << i;
	// cout<<endl<<endl;
	out.close();
	return 0;
}