Cod sursa(job #2033308)

Utilizator GinguIonutGinguIonut GinguIonut Data 6 octombrie 2017 17:01:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.53 kb
#include <stdio.h>
#include <stdlib.h>

#define nMax 100001

FILE *in, *out;

int viz[nMax];

typedef struct node {
    int data;
    struct node* next;
} node;

node* head[nMax];

node* create(int data, node* next)
{
    node* new_node = (node*)malloc(sizeof(node));
    if(new_node == NULL) {
        fprintf(out, "Error when creating a new node\n");
        return NULL;
    }

    new_node->data = data;
    new_node->next = next;
    return new_node;
}

node* insertFront(int data, node* head)
{
    node* new_node = create(data, head);
    head = new_node;
    return head;
}

void dfs(int current, int father)
{
    viz[current] = 1;

    node* cursor = head[current];
    while(cursor != NULL) {
        int son = cursor->data;
        cursor = cursor->next;
        if(son == father) {
            continue;
        }

        if(viz[son] == 0) {
            dfs(son, current);
        }
    }

}

int main()
{
    in = fopen("dfs.in", "r");
    out = fopen("dfs.out", "w");

    int n, m, a, b;
    fscanf(in, "%d%d", &n, &m);


    int i;

    for(i=0; i<nMax; i++) {
        head[i] = NULL;
    }

    for(i=1; i<=m; i++) {
        fscanf(in, "%d%d", &a, &b);
        head[b] = insertFront(a, head[b]);
        head[a] = insertFront(b, head[a]);
    }

    int conex_components = 0;
    for(i=1; i<=n; i++) {
        if(viz[i] == 0) {
            dfs(i, 0);
            conex_components++;
        }
    }

    fprintf(out, "%d", conex_components);

    return 0;
}