Cod sursa(job #214597)

Utilizator savimSerban Andrei Stan savim Data 15 octombrie 2008 11:23:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h> 
#include <stdlib.h>

#define maxl 100010

int n,m,i,p,q;
int deg[maxl], fol[maxl];
int * g[maxl];

void dfs(int p) {
     int i;
     for (i = 0; i < deg[p]; i++)
         if (!fol[g[p][i]]) {
            fol[g[p][i]] = 1;
            dfs(g[p][i]);
         }
}

int main() {
    
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    
    scanf("%d %d",&n,&m);
    for (i = 0; i < m; i++) {
        scanf("%d %d",&p,&q);
        deg[p]++;
        deg[q]++;
    }
    
    fclose(stdin);

    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 = 0; i <= n; i++) deg[i] = 0;
    for (i = 0; i < m; i++) {
        scanf("%d %d",&p,&q);
        g[p][deg[p]++] = q;
        g[q][deg[q]++] = p;
    }

    int nr = 0;
    for (i = 1; i <= n; i++)
        if (!fol[i]) {
           fol[i] = 1;
           dfs(i);
           nr++;
        }

    printf("%d\n",nr);

    for (i = 1; i <= n; i++)
        free(g[i]);
    
    return 0;
}