#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAX_NODES 101000
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(LinkedList *list) {
list->head = NULL;
list->tail = NULL;
list->size = 0;
}
void add_nth_node(LinkedList *list, int n, void *new_data) {
Node *prev, *curr;
Node *new_node;
if (list == NULL) {
return;
}
if (n > list->size) {
n = list->size;
} else if (n < 0) {
return;
}
curr = list->head;
prev = NULL;
while (n > 0) {
prev = curr;
curr = curr->next;
--n;
}
new_node = malloc(sizeof(Node));
if (new_node == NULL) {
perror("Not enough memory to add element!");
exit(-1);
}
new_node->data = new_data;
new_node->next = curr;
if (prev == NULL) {
/* Adica n == 0. */
list->head = new_node;
} else {
prev->next = new_node;
}
if (new_node->next == NULL) {
list->tail = new_node;
}
list->size++;
}
Node* remove_nth_node(LinkedList *list, int n) {
Node *prev, *curr;
if (list == NULL) {
return NULL;
}
if (list->head == NULL) { /* Lista este goala. */
return NULL;
}
if (n > list->size - 1) {
n = list->size - 1;
} else if (n < 0) {
return NULL;
}
curr = list->head;
prev = NULL;
while (n > 0) {
prev = curr;
curr = curr->next;
--n;
}
if (prev == NULL) {
/* Adica n == 0. */
list->head = curr->next;
} else {
prev->next = curr->next;
if (prev->next == NULL) {
list->tail = prev;
}
}
list->size--;
return curr;
}
int get_size(LinkedList *list) {
if (list == NULL) {
return -1;
}
return list->size;
}
void free_list(LinkedList **pp_list) {
struct Node *currNode;
if (pp_list == NULL || *pp_list == NULL) {
return;
}
while(get_size(*pp_list) > 0) {
currNode = remove_nth_node(*pp_list, 0);
free(currNode);
}
free(*pp_list);
*pp_list = NULL;
}
void init_list_graph(ListGraph *graph, int nodes) {
graph->nodes = nodes;
graph->neighbors = malloc(nodes * sizeof(LinkedList));
if (graph->neighbors == NULL) {
perror("Not enough memory to initialize the adjacency list!");
exit(-1);
}
for (int i = 0; i < nodes; ++i) {
graph->neighbors[i] = malloc(sizeof(LinkedList));
if (graph->neighbors[i] == NULL) {
perror("Not enough memory to initialize the adjacency list!");
exit(-1);
}
init_list(graph->neighbors[i]);
}
}
void add_edge_list_graph(ListGraph *graph, int src, int *dest) {
add_nth_node(graph->neighbors[src] , 0x7fffffff, dest);
}
int has_edge_list_graph(ListGraph *graph, int src, int dest) {
Node *head = graph->neighbors[src]->head;
int crt_node;
while (head != NULL) {
crt_node = *(int *)head->data;
if (crt_node == dest) {
return 1;
}
head = head->next;
}
return 0;
}
LinkedList* get_neighbours_list_graph(ListGraph *graph, int node) {
return graph->neighbors[node];
}
void remove_edge_list_graph(ListGraph *graph, int src, int dest) {
struct Node *curr;
int poz;
poz = 0;
curr=(graph->neighbors[src])->head;
while( curr!=NULL) {
if(*((int *)curr->data) == dest) {
remove_nth_node(graph->neighbors[src],poz);
}
poz++;
curr = curr->next;
}
}
void clear_list_graph(ListGraph *graph) {
int i;
for(i = 0; i < graph->nodes; i++) {
free_list(&graph->neighbors[i]);
}
free(graph->neighbors);
}
void dfs_list_graph(ListGraph *lg, int node, int *visited, int *t_desc, int *t_fin, int *time) {
struct Node *curr;
int i;
curr = lg->neighbors[node]->head;
visited[node] = 1;
t_desc[node] = (*time)++;
while(curr!=NULL) {
i = *((int*)curr->data);
if(visited[i] == 0) {
dfs_list_graph(lg,i,visited,t_desc,t_fin,time);
}
curr = curr->next;
}
t_fin[node] = (*time)++;
}
int main(void) {
int nodes, edges, node, i;
int x[MAX_NODES], y[MAX_NODES];
int visited[MAX_NODES];
int parents[MAX_NODES], dist[MAX_NODES],t_desc[MAX_NODES],t_fin[MAX_NODES];
int time;
FILE *fin,*fout;
fin = fopen("dfs.in","rt");
if(fin==NULL) {
printf("NU se poate deschide fisierul");
return 0;
}
fout = fopen("dfs.out","wt");
if(fout==NULL) {
printf("NU se poate deschide fisierul");
return 0;
}
ListGraph *lg = malloc(sizeof(ListGraph));
fscanf(fin,"%d %d", &nodes, &edges);
init_list_graph(lg, nodes);
for (int i = 0; i < edges; ++i) {
fscanf(fin,"%d %d", &x[i], &y[i]);
x[i]=x[i]-1;
y[i]=y[i]-1;
add_edge_list_graph(lg, x[i], &y[i]);
add_edge_list_graph(lg, y[i], &x[i]);
}
for(i = 0; i <= nodes; i++){
dist[i] = 0;
visited[i] = 0;
}
time = 0;
int nr;
nr = 0;
for(i = 0; i< nodes; i++) {
if(visited[i] == 0) {
dfs_list_graph(lg, i, visited, t_desc, t_fin, &time);
nr++;
}
}
fprintf(fout,"%d", nr);
clear_list_graph(lg);
free(lg);
fclose(fin);
fclose(fout);
return 0;
}