Cod sursa(job #2216077)

Utilizator FaneCelMareStefan FaneCelMare Data 25 iunie 2018 10:10:18
Problema Parcurgere DFS - componente conexe Scor 80
Compilator c Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <stdlib.h>
int n, m, viz[100000];
typedef struct nod {
    int info;
    struct nod *urm;
} nod;
nod* v[100000];
void dfs(int n) {
    viz[n] = 1;
    nod* p;
    p = malloc(sizeof(nod));
    for (p = v[n]; p != NULL; p = p ->urm) {
        if (viz[p->info] == 0) {
            dfs(p->info);
        }
    }
}
int main()
{
    FILE*in = fopen("dfs.in", "r");
    FILE*out = fopen("dfs.out", "w");
    fscanf(in, "%d %d", &n, &m);
    int a, b, i;
    for (i = 0; i < m; i++) {
        fscanf(in, "%d %d", &a, &b);
        nod* p;
        p = malloc(sizeof(nod));
        p->info = b;
        p->urm = v[a];
        v[a] = p;
        p = malloc(sizeof(nod));
        p->info = a;
        p->urm = v[b];
        v[b] = p;
    }
    a = 0;
    for (i = 1; i <= n; i++) {
        if (viz[i] == 0) {
            dfs(i);
            a++;
        }
    }
    fprintf(out, "%d", a);
    return 0;
}