Pagini recente » Cod sursa (job #3268637) | Cod sursa (job #250926) | Cod sursa (job #1709870) | Cod sursa (job #2592103) | Cod sursa (job #1431626)
#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;
}