Cod sursa(job #146645)

Utilizator floflowfloflofloflofloflo floflow Data 1 martie 2008 22:45:05
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
   #include <stdio.h>  
    
  int n, m, viz[100005], cnt;  
    
  typedef struct nod  
   {  
       int x;  
       nod *a;  
 } *pNod;  
   pNod v[100005];  
    
  void citire()  
   {  
       freopen("dfs.in","r",stdin);  
     freopen("dfs.out","w",stdout);  
       scanf("%d %d",&n,&m);  
       int i, x, y;  
       pNod p;  
        
       for (i = 1; i <= m; i++)  
      {  
          scanf("%d %d",&x,&y);  
          p = new nod;  
           p -> x = x;  
          p -> a = v[y];  
          v[y] = p;  
         p = new nod;  
         p -> x = y;  
         p -> a = v[x];  
          v[x] = p;  
       }  
  }  
   
  void DFS(int nod)  
  {  
      pNod p;  
       viz[nod] = 1;  
     for (p = v[nod]; p != NULL; p = p -> a) if (!viz[p -> x]) DFS(p -> x);  
 }     
   
 int main()  
 {  
      citire();  
      int i;  
    for (i = 1; i <= n; i++) if (!viz[i]) { cnt++; DFS(i);}  
     printf("%d\n",cnt);  
    return 0;  
  }