Cod sursa(job #212225)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 4 octombrie 2008 17:43:53
Problema Parcurgere DFS - componente conexe Scor 50
Compilator c Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>   
  
#define FIN "dfs.in"   
#define FOUT "dfs.out"   
  
#define NMAX 1005   
  
int n,m;   
int 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); 
    int i;     
    for (i=1;i<=m;++i)      
         {      
         scanf("%d %d",&x,&y);      
         a[x][y]=a[y][x]=1;      
         }      
}      
     
void DFS(int x)      
{      
    int i;
    viz[x]=1;      
    for (i=1;i<=n;++i)    
         if (!viz[i] && a[x][i])    
             DFS(i);      
}         
     
void solve()
{
    int i;
    for (i=1;i<=n;++i)
         if (!viz[i])
             {
               nr++;
               DFS(i);
             }
}
                  
int main()      
{      
    read_data();      
    solve();
    printf("%d", nr);      
    return 0;      
}