Cod sursa(job #146361)

Utilizator floringh06Florin Ghesu floringh06 Data 1 martie 2008 16:38:36
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>   
#include <cstdlib>

using namespace std;

#define FIN "dfs.in"
#define FOUT "dfs.out"
#define MAX_N 100005
  
typedef struct nod   
{   
    int d;   
    nod *a;   
} *adrnod;   

adrnod T[100005], p;     
  
int N, M, Nc, i;
int V[100005];   
   
    void read()   
    {
         int i, x, y;      
         scanf("%d %d", &N, &M);   
         
         for (i = 1; i <= M; i++)   
         {   
             scanf("%d %d", &x, &y);   
             p = new nod; p -> d = x; p -> a = T[y]; T[y] = p;   
             p = new nod; p -> d = y; p -> a = T[x]; T[x] = p;   
         }   
    }   
  
    void DFS(int nod)   
    {   
         adrnod it;
         V[nod] = 1;   
         for (it = T[nod]; it != NULL; it = it -> a) 
             if (!V[it -> d]) DFS(it -> d);   
    }      
  
    int main()   
    {   
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
    
        read();    
        for (i = 1; i <= N; i++) 
               if (!V[i]) 
               { 
                          Nc++; 
                          DFS(i);
               }   
        
        printf("%d\n", Nc);   
        return 0;   
    }