Cod sursa(job #214592)

Utilizator CezarMocanCezar Mocan CezarMocan Data 15 octombrie 2008 11:20:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 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 i;
     
     for (i=0; i<d[nod]; i++) {
         if ( viz[ g[nod][i] ] == 0 ) {
            viz[ g[nod][i] ] = nr;     
            dfs(g[nod][i]);
         }
     }
}

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]++;
    }    
    
    nr=1;
    
    for (i=1; i<=n; i++)
        if ( viz[i] == 0 ) {
           viz[i]=nr;
           dfs(i);
           nr++;
        }
    
    printf("%d\n", nr-1);
    
    return 0;    
}