Pagini recente » Cod sursa (job #2942253) | Cod sursa (job #2092079) | Cod sursa (job #2219938) | Cod sursa (job #1718347) | Cod sursa (job #1234117)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct node {
int id;
struct node *next;
};
void add_node(struct node **adj_list, int x, int y)
{
struct node *new_node = malloc(sizeof(struct node));
new_node->id = y;
new_node->next = adj_list[x];
adj_list[x] = new_node;
}
void free_list(struct node **list)
{
if (!*list)
return;
if ((*list)->next)
free_list(&(*list)->next);
free(*list);
*list = NULL;
}
void dfs(int node, int *visited_nodes, struct node **adj_list)
{
struct node *it;
visited_nodes[node] = 1;
for (it = adj_list[node]; it; it = it->next)
if (!visited_nodes[it->id])
dfs(it->id, visited_nodes, adj_list);
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int i, N, M;
scanf("%d %d", &N, &M);
struct node **adj_list = calloc(N+1, sizeof(struct node*));
assert(adj_list);
for (i = 1; i <= M; ++i) {
int x, y;
scanf("%d %d", &x, &y);
add_node(adj_list, x, y);
add_node(adj_list, y, x);
}
int *visited_nodes = calloc(N+1, sizeof(int));
int count = 0;
for (i = 1; i <= N; ++i)
if (!visited_nodes[i]) {
++count;
dfs(i, visited_nodes, adj_list);
}
printf("%d\n", count);
// Free memory
for (i = 1; i <= N; ++i)
free_list(&adj_list[i]);
free(adj_list);
free(visited_nodes);
return 0;
}