Cod sursa(job #2219425)

Utilizator PasarelAlex Oltean Pasarel Data 8 iulie 2018 20:42:02
Problema Parcurgere DFS - componente conexe Scor 80
Compilator c Status done
Runda Arhiva educationala Marime 1.33 kb
#include <stdio.h>
#include <stdlib.h>

struct list {
    int node;
    struct list *next;
}* list[100000];
char visited[100000];

void add_neighbour(int vertex, int neighbour) {
    struct list *aux;
    aux = malloc(sizeof(struct list));
    aux->next = list[vertex];
    aux->node = neighbour;
    list[vertex] = aux;
}

void dfs(int vertex) {
    struct list *aux;
    aux = list[vertex];
    visited[vertex] = 1;
    for (aux = list[vertex]; aux != NULL; aux = aux->next)
        if (!visited[aux->node])
            dfs(aux->node);
}

void freemem(struct list *list) {
    struct list *aux;
    while (list != NULL) {
        aux  = list;
        list = list->next;
        free(aux);
    }
}

int main()
{
    int conexe = 0;
    int n, m;
    int k, j;
    int i;
    FILE *in;
    FILE *out;

    in = fopen("dfs.in", "r");
    fscanf(in, "%d %d", &n, &m);
    for (i = 0; i < m; i++) {
        fscanf(in, "%d %d", &k, &j);
        add_neighbour(k, j);
        add_neighbour(j, k);
    }
    fclose(in);

    for (i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
            conexe++;
        }
    }
    out = fopen("dfs.out", "w");
    fprintf(out, "%d", conexe);
    fclose(out);
    for (i = 1; i <= n; i++) {
        freemem(list[i]);
    }
    return 0;
}