Cod sursa(job #803395)

Utilizator alexclpAlexandru Clapa alexclp Data 27 octombrie 2012 15:02:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <stdlib.h>

#define N 100001

FILE *in;
FILE *out;

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

struct list *v[N];
int viz[N];
int n, m;

void add(int x, int y)
{
    struct list *nou = (struct list*)malloc(sizeof(struct list));
    nou->data = y;
    nou->next = v[x];
    v[x] = nou;
}

void citire()
{
    int i, x, y;

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

    for (i = 1; i <= m; i++) {
        fscanf(in, "%d %d", &x, &y);
        add(y, x);
        add(x, y);
    }
}

void DFS(int x)
{
    viz[x] = 1;
    struct list *p;

    for (p = v[x]; p != NULL; p = p->next) {
        if (!viz[p -> data]) {
            DFS(p -> data);
        }
    }
}

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

    citire();

    int i;
    int count = 0;

    for (i = 1; i <= n; i++) {
        if (!viz[i]) {
            count ++;
            DFS(i);
        }
    }

    fprintf(out, "%d\n", count);

    return 0;
}