Cod sursa(job #291703)

Utilizator mihneapPetre Mihnea mihneap Data 30 martie 2009 10:55:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
    #include <stdio.h>  
    #define nmax 100005  
    int use[nmax];  
    struct nod  
    {  
        int varf;  
        nod *adr;  
    } *q[nmax];  
      
   void add(long x, long y)  
  
 {  
       nod *aux;  
       aux=new nod;  
       aux->varf=y;  
      aux->adr=q[x];  
     q[x]=aux;  
   }  
     
   void dfs(long a)  
   {  
       nod *aux;  
       aux=q[a];  
       use[a]=1;  
       while (aux!=NULL)  
       {  
          if (!use[aux->varf]) dfs(aux->varf);  
           aux=aux->adr;  
      }  
   }  
     
   int main()  
   {  
       long nr=0,n,m,i,a,b;  
       freopen("dfs.in","r",stdin);  
       freopen("dfs.out","w",stdout);  
       scanf("%ld%ld",&n,&m);  
       for (i=1;i<=m;i++)  
       {  
           scanf("%ld%ld",&a,&b);  
           add(a,b);  
           add(b,a);  
       }  
       for (i=1;i<=n;i++)  
           if (!use[i]) {  
               dfs(i);  
               nr++;  
           }  
       printf("%ld\n",nr);  
       return 0;  
   }