Cod sursa(job #2106570)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 15 ianuarie 2018 22:08:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>

struct nod{
    int info;
    struct nod* urm;
};

struct nod *inserare_inceput(struct nod* p,int x){
    if(p==NULL){
        struct nod * elem= (struct nod *) malloc(sizeof(struct nod));
        elem->info=x;
        elem->urm=NULL;
        return elem;
    }
    struct nod* elem=(struct nod *) malloc(sizeof(struct nod));
    elem->info=x;
    elem->urm=p;
    return elem;
}

void citire(int *n, int *m, struct nod ***v){
    FILE * fin = fopen("dfs.in", "rt");
    if(fin == NULL) {
        printf("The file can't be opened!");
        exit(EXIT_FAILURE);
    }
    fscanf(fin, "%d%d", n, m);
    *v = (struct nod**) malloc(( (*n)+1) * sizeof(struct nod*));
    int k,i,j;
    for(k=1;k<=*m;k++){
        fscanf(fin, "%d%d", &i, &j);
        (*v)[i]=inserare_inceput((*v)[i],j);
        (*v)[j]=inserare_inceput((*v)[j],i);
    }
    fclose(fin);
}

void DFS(int x, struct nod **v, int *viz){
    viz[x]=1;
    struct nod* parcurg=v[x];
    while(parcurg){
        if(viz[parcurg->info] == 0)
            DFS(parcurg->info, v, viz);
        parcurg=parcurg->urm;
    }
}

int main(){
    int n, m, contor = 0;
    struct nod **v = NULL;
    citire(&n, &m, &v);
    int * viz = (int *) calloc((n + 1),  sizeof(int));
    for(int i = 1; i <= n; i++){
        if(viz[i]==0){
            ++contor;
            DFS(i, v, viz);
        }
    }
    FILE *fout = fopen("dfs.out", "wt");
    if(fout == NULL) {
        printf("The file can't be opened!");
        exit(EXIT_FAILURE);
    }
    fprintf(fout, "%d", contor);
    fclose(fout);
    return 0;
}