Cod sursa(job #316485)

Utilizator klamathixMihai Calancea klamathix Data 19 mai 2009 21:04:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<cstdio>
#include<vector>
#define MAXN 100005
using namespace std;

int i , j , k , path[MAXN] ,comp , Sum , N , M , a, b;

vector <int> G[MAXN];

void read() 
{
     scanf("%d %d",&N ,&M);
     for( ; M -- ; ) {
          scanf("%d %d",&a,&b);
          G[a].push_back(b),G[b].push_back(a);
          }
}

void DFS(int X)
{
     int j;
     
     if(path[X]) return ;
     
     path[X] = 1;
     
     for( j = 0 ; j < G[X].size() ; j++)
          if(!path[G[X][j]])
            DFS(G[X][j]);
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    
    read();
    
    for( i = 1 ; i <= N ; i++){
    if(!path[i]) {comp ++, DFS(i);}
}
    printf("%d\n",comp);

return 0;
}