Cod sursa(job #1234117)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 26 septembrie 2014 18:40:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.45 kb
#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;
}