Cod sursa(job #214582)

Utilizator CezarMocanCezar Mocan CezarMocan Data 15 octombrie 2008 10:52:08
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int n, i, a, b, m, nr, j;

int *g[100100];

int deg[100100], d[100100], viz[100100];



void dfs(int nod, int nr) {
     int i;
     
     for (i=0; i<d[nod]; i++) {
         if ( viz[ g[nod][i] ] == 0 ) {
            viz[ g[nod][i] ] = 1;     
            dfs(nod, nr);
         }
     }
         

     
}



int main() {
    
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    
    scanf("%d%d", &n, &m);
    
    for (i=1; i<=m; i++) {
        scanf("%d%d", &a, &b);
        deg[a]++;
        deg[b]++;    
    }
    
    for (i=1; i<=n; i++)
        g[i]=(int *) malloc(sizeof (int) * deg[i] );  
        
    freopen("dfs.in", "r", stdin);
    
    scanf("%d%d", &n, &m);
    
    for (i=1; i<=m; i++) {
        scanf("%d%d", &a, &b);    
        
        g[a][d[a]]=b;
        d[a]++;
        
        g[b][d[b]]=a;
        d[b]++;
    }    
    
/*    for (i=1; i<=n; i++) {
        for (j=0; j<d[i]; j++)
            printf("%d ",g[i][j]);
        printf("\n");    
    }*/
    
    for (i=1; i<=n; i++)
        if ( viz[i] == 0 ) {
           dfs(i, nr);
           nr++;
        }
    
    printf("%d\n", nr);
    
    return 0;    
}