Pagini recente » Diferente pentru utilizator/eugenstoica intre reviziile 10 si 11 | Monitorul de evaluare | Monitorul de evaluare | Diferente pentru onis-2015/solutii-runda-1 intre reviziile 45 si 46 | Cod sursa (job #2594964)
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
void *data;
struct Node *next;
} Node;
typedef struct {
Node *head;
Node *tail;
int size;
} LinkedList;
typedef struct {
LinkedList **neighbors;
int nodes;
} ListGraph;
void init_list_graph(ListGraph *graph, int nodes) {
graph->nodes = nodes;
graph->neighbors = malloc(nodes * sizeof(LinkedList*));
for(int i = 1; i <= nodes; ++i) {
graph->neighbors[i] = malloc(sizeof(LinkedList));
graph->neighbors[i]->head = NULL;
graph->neighbors[i]->tail = NULL;
graph->neighbors[i]->size = 0;
}
}
void add_edge_list_graph(ListGraph *graph, int src, int *dest) {
Node *nod;
nod = malloc(sizeof(Node));
nod->data = dest;
nod->next = NULL;
Node *p;
p = graph->neighbors[src]->head;
if(p == NULL) {
graph->neighbors[src]->head = nod;
graph->neighbors[src]->tail = nod;
graph->neighbors[src]->size++;
return;
}
while(p->next != NULL) {
p = p->next;
}
p->next = nod;
graph->neighbors[src]->tail = nod;
graph->neighbors[src]->size++;
}
void dfs_list_graph(ListGraph *lg, int node, int *visited) {
Node *p;
p = lg->neighbors[node]->head;
visited[node] = 1;
while(p != NULL) {
if(visited[*(int*)p->data] == -1){
dfs_list_graph(lg, *(int*)p->data, visited);
}
p = p->next;
}
}
int main() {
int n, m, x[101], y[101], visited[101];
ListGraph *lg;
lg = malloc(sizeof(ListGraph));
FILE *in = fopen("dfs.in", "rt");
FILE *out = fopen("dfs.out", "wt");
fscanf(in, "%d%d", &n, &m);
for(int i = 1; i <= m; ++i){
fscanf(in, "%d%d", &x[i], &y[i]);
}
init_list_graph(lg, n);
for(int i = 1; i <= m; ++i){
add_edge_list_graph(lg, x[i], &y[i]);
add_edge_list_graph(lg, y[i], &x[i]);
}
for(int i = 1; i <= n; ++i){
visited[i] = -1;
}
int count = 0;
for(int i = 1; i <= n; ++i){
if(visited[i] == -1){
dfs_list_graph(lg, i, visited);
count++;
}
}
fprintf(out, "%d", count);
return 0;
}