Cod sursa(job #313064)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 7 mai 2009 21:34:58
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <stdio.h>
#define Nmax 1000
int x,cnt,viz[10000],y,m,n,A[Nmax][Nmax];
void DFS(int q)
{ int i;
     viz[q]=1;
     for(i=1;i<=A[q][0];i++)
         if(!viz[A[q][i]])
         DFS(A[q][i]);
        
       
}        
int main()
{int i;
    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][0]++;A[x][A[x][0]]=y;
        A[y][0]++;A[y][A[y][0]]=x;
      }
    for(i=1; i<=n; i++)
      if(!viz[A[i][0]]) ++cnt,DFS(i);   
    printf("%d\n",cnt); 
    return 0;
}