Cod sursa(job #237479)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 29 decembrie 2008 21:23:35
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<stdio.h>
#include<stdlib.h>

int *a[100001],nr,n,m,i,x,y,s,q[100001],fol[100001];

void citire();
void df(int);
void afisare();

int main(){
    citire();
    for (int i=1;i<=n;i++)
        if (!fol[i])
           df(i),nr++;
    afisare();
    return 0;
}

void citire(){
int i;
     freopen("dfs.in","r",stdin);
     scanf("%d %d ",&n,&m);
     for (i=1;i<=n;i++){
         a[i]=(int*)malloc(sizeof(int));
         a[i][0]=0;    
     }
     for (i=1;i<=m;i++){
         scanf("%d %d", &x,&y);
         a[x][0]++;
         a[x]=(int*) realloc(a[x],(a[x][0]+1)*sizeof(int));
         a[x][a[x][0]]=y;
         a[y][0]++;
         a[y]=(int*) realloc(a[y],(a[y][0]+1)*sizeof(int));
         a[y][a[y][0]]=x;
         
     }
}

void df(int w){ 
int j;
    fol[w]=1;
    for (j=1;j<=a[x][0];j++)
             if (!fol[a[x][j]])
                 df(a[x][j]);
}

void afisare(){
     freopen("dfs.out","w",stdout);
     printf("%d\n",nr);
}