Cod sursa(job #1622719)

Utilizator Cristian214Cristian Toth Cristian214 Data 1 martie 2016 13:50:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100001
typedef struct node{
    int info;
    struct node *next;
}node;

node *G[NMAX];
int  viz[NMAX];

void dfs(int nod){
    viz[nod] = 1;
    node *p = NULL;
    for(p = G[nod]; p != NULL; p = p->next)
        if(!viz[p->info])
            dfs(p->info);
}

int main(){
    int n, m, i, j;
    FILE *fpi = freopen("dfs.in", "r", stdin);
    scanf("%d %d", &n, &m);
    for(; m; m--){
        scanf("%d %d", &i, &j);
        node *p = (node*)malloc(sizeof(node));
        p->next = G[i];
        p->info = j;
        G[i] = p;
        node *p2 = (node*)malloc(sizeof(node));
        p2->next = G[j];
        p2->info = i;
        G[j] = p2;
    }
    fclose(fpi);
    int cnt = 0;
    for (i = 1; i <= n; i++)
        if(!viz[i]){
            dfs(i);
            cnt++;
        }
    FILE *fpo = freopen("dfs.out", "w", stdout);
    printf("%d", cnt);
    fclose(fpo);
    for(i = 1; i <= n; i++){
        node *p = NULL;
        for(p = G[i]; p != NULL; p = p->next)
            free(p);
    }
    return 0;
}