Cod sursa(job #316502)

Utilizator klamathixMihai Calancea klamathix Data 19 mai 2009 21:27:29
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<cstdio>
#include<vector>

#define MAXN 100005
using namespace std;

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

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 , top = 0 , ok ;
     
     stack[++top] = X;
      
     while(top) 
     {
                X = stack[top] , ok = 0 , path[X] = 1;
                
                for( j = 0 ; j < G[X].size() ; ++j)
                     if(!path[G[X][j]] ) {ok = 1 ; break;}
                
                if(ok) stack[++top] = G[X][j] ;
                       else --top;
     }
}
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;
}