Cod sursa(job #544681)

Utilizator slycerdan dragomir slycer Data 1 martie 2011 22:02:39
Problema Parcurgere DFS - componente conexe Scor 15
Compilator c Status done
Runda Arhiva educationala Marime 1.13 kb
/* 
 * File:   main.c
 * Author: slycer
 *
 * Created on March 1, 2011, 11:52 PM
 */

#include <stdio.h>
#include <stdlib.h>

struct nod{
    int j; 
    struct nod * next; 
};

char * marcat; 
struct nod * d;
/*
 * 
 */

void dfs( int v ){
    marcat[v] = 1; 
    struct nod * aux = d[v].next; 
    while ( aux ){
        if ( !marcat[aux->j]){
            dfs( aux->j ); 
        }
        aux = aux->next;
    }
}

int main(int argc, char** argv) {

    FILE * in = fopen("dfs.in","r");
    FILE * out = fopen("dfs.out","w"); 
    d = calloc( 100001,sizeof( struct nod ) );
    marcat = calloc(100001,sizeof(char)); 
    
    int n,m; 
    fscanf(in,"%d%d",&n, &m);
    int i; 
    for ( i=0; i<m; i++){
        int x,y; 
        fscanf(in,"%d%d",&x,&y);
        struct nod * aux = calloc(1,sizeof( struct nod )); 
        aux->next = d[x].next; 
        aux->j = y; 
        d[x].next = aux; 
    }
    
    int count = 0; 
    for ( i=1; i<=n; i++){
        if ( !marcat[i]){
            dfs( i ); 
            count++; 
        }
    }
    
    fprintf(out,"%d",count); 
    
    fclose( in ); 
    fclose( out ); 
    
    return (EXIT_SUCCESS);
}