Cod sursa(job #237464)

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

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

void citire();
void bf(int);
void afisare();

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

void citire(){
int i;
     freopen("bfs.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;
     }
}

void bf(int w){ 
int i,j,u;
     q[0]=w;
     fol[w]=1;
     for (i=0,u=0;i<=u;i++){
         x=q[i];
         for (j=1;j<=a[x][0];j++)
             if (!fol[a[x][j]]){
                fol[a[x][j]]=1;
                q[++u]=a[x][j];
             }
     }
}

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