Cod sursa(job #247164)

Utilizator hasegandaniHasegan Daniel hasegandani Data 22 ianuarie 2009 11:36:55
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<stdio.h>

#define nmax 100000

int v[nmax][1000],viz[nmax],n;

void dfs(int k,int l)
{
     for(int i=1;i<=v[k][0];++i)
	     if (!viz[v[k][i]])
			 {
                         viz[v[k][i]]=l;
                         dfs(v[k][i],l);
                         }
}

int main()
{
    int a,b,m,x=0;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--)
            {
            scanf("%d%d",&a,&b);
            v[a][++v[a][0]]=b;
            v[b][++v[b][0]]=a;
            }
    for(int i=1;i<=n;++i)
            if (!viz[i])
               {
               viz[i]=++x;
               dfs(i,x);
               }
    printf("%d\n",x);
    return 0;
}