Cod sursa(job #347475)

Utilizator miticaMitica mitica Data 12 septembrie 2009 13:04:39
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <stdio.h>

int n,m,x,y,a[1000][1000],p,nc,vb,v[100000],i;

void DF(int k)
{
     int i;
     v[k]=1;
     for (i=1;i<=n;i++)
         if (!v[i] && a[k][i])
            DF(i);
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","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;
        }     
    for (i=1;i<=n;i++)
        if (!v[i])
           {
                  nc++;
                  DF(i);
           }
    printf("%d", nc);
    return 0;
}