Cod sursa(job #147083)

Utilizator HoriaClementHoriaC HoriaClement Data 2 martie 2008 16:11:56
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>   
  
int a[1005][1005], n, m, viz[1005], cnt;   
  
void citire()   
{   
    freopen("dfs.in","r",stdin);   
    freopen("dfs.out","w",stdout);   
    scanf("%d %d",&n,&m);   
    int i, x, y;   
    for (i = 1; i <= m; i++)   
    {   
        scanf("%d %d",&x,&y);   
        a[x][y] = a[y][x] = 1;   
    }   
}   
  
void DFS(int nod)   
{   
    int i;   
    viz[nod] = 1;   
    for (i = 1; i <= n; i++) if (!viz[i] && a[nod][i]) DFS(i);   
}      
  
int main()   
{   
    citire();   
    int i;   
    for (i = 1; i <= n; i++) if (!viz[i]) { cnt++; DFS(i);}   
    printf("%d\n",cnt);   
    return 0;   
}