Cod sursa(job #1607108)

Utilizator robert.stefanRobert Stefan robert.stefan Data 20 februarie 2016 20:29:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.14 kb
#include <stdio.h>

#define IN "dfs.in"
#define OUT "dfs.out"
#define MAXN 100001

typedef struct _GRAPH{
    int node;
    struct _GRAPH *next;
} GRAPH;

int n, m, counter = 0, seen [MAXN];
GRAPH *graph [MAXN];

inline void add (int location, int node0){
    GRAPH *p = (GRAPH*) malloc (sizeof (GRAPH));

    p -> node = node0;
    p -> next = graph [location];
    graph [location] = p;
}

void read (void){
    int i, edge1, edge2;

    scanf ("%d%d", &n, &m);

    for (i = 1; i <= m; ++i){
        scanf ("%d%d", &edge1, &edge2);
        add (edge1, edge2);
        add (edge2, edge1);
    }
}

void dfs (int node0){
    GRAPH *node = graph [node0];
    seen [node0] = 1;

    while (node){
        if (! seen [node -> node])
            dfs (node -> node);
        node = node -> next;
    }
}

int main (void){
    freopen (IN, "r", stdin);
    freopen (OUT, "w", stdout);

    read();

    int i;
    for (i = 1; i <= n; ++ i)
        if (!seen [i]){
            ++ counter;
            dfs (i);
        }

    printf ("%d", counter);

    fclose (stdin);
    fclose (stdout);
    return 0;
}