Cod sursa(job #212219)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 4 octombrie 2008 17:37:10
Problema Parcurgere DFS - componente conexe Scor 5
Compilator c Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>

#define FIN "dfs.in"
#define FOUT "dfs.out"

#define NMAX 1015

int n,m;
int i,nr;
int viz[NMAX];
int a[NMAX][NMAX];
int x,y;

void read_data()   
{   
    freopen(FIN,"r",stdin);   
    freopen(FOUT,"w",stdout);   
    scanf("%d %d",&n,&m);   
    for (i=1;i<=m;++i)   
         {   
         scanf("%d %d",&x,&y);   
         a[x][y]=a[y][x]=1;   
         }   
}   
  
void DFS(int x)   
{   
    viz[x]=1;   
    for (i=1;i<=n;++i) 
         if (!viz[i] && a[x][i]) 
             DFS(i);   
}      
  
int main()   
{   
    read_data();   
    for (i=1;i<=n;++i) 
         if (!viz[i]) 
             { 
               nr++; 
               DFS(i);
             }   
    printf("%d", nr);   
    return 0;   
}