Cod sursa(job #1743787)

Utilizator andrei4_bulzanAndrei Bulzan andrei4_bulzan Data 18 august 2016 19:02:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.2 kb
#include <stdio.h>
int n, m, viz[100001], cnt;

typedef struct nod
{
    int info;
    struct nod *next;
} nod_t;
nod_t *v[100001];

nod_t* add(nod_t *l, int x)
{
    nod_t *p = malloc(sizeof(nod_t));
    p->info = x;
    p->next = l;
    l = p;
    return l;
}

void read()
{
    FILE *f;
    int i, x, y;
    f = fopen("dfs.in", "r");
    fscanf(f, "%d %d", &n, &m);
    for(i=1; i<=m; i++)
    {
        fscanf(f, "%d %d", &x, &y);
        v[x] = add(v[x], y);
        v[y] = add(v[y], x);
    }

    fclose(f);

}
/*
void write()
{
    int i;
    nod_t *p;
    for(i=1; i<=n; i++)
    {
        p = v[i];
        printf("%d: ", i);
        while(p != NULL)
        {
            printf("%d ", p->info);
            p = p->next;
        }
        putchar('\n');
    }
}
*/
void DFS(int nod)
{
    nod_t *p;
    viz[nod] = 1;
    for(p = v[nod]; p != NULL; p = p->next)
        if(!viz[p->info])
            DFS(p->info);
}

int main()
{
    read();
    int i;
    for(i=1; i<=n; i++)
        if(!viz[i])
        {
            cnt++;
            DFS(i);
        }

    FILE *g = fopen("dfs.out", "w");
    fprintf(g, "%d", cnt);

    fclose(g);
}