Cod sursa(job #146858)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 2 martie 2008 12:08:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <stdio.h>
#include <vector>
#include <bitset>
#define nMax 100005

using namespace std;

vector <long>v[nMax];
bitset <131072> viz;

void DFS(long x){
     if (viz[x])return;
     viz[x]=1;
     for_each(v[x].begin(),v[x].end(),DFS);
}

int main(){
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    
    long n,m,i,x,y,conex=0;
    
    scanf("%ld %ld",&n,&m);
    for (i=1;i<=m;i++){
        scanf("%ld %ld",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for (i=1;i<=n;i++)
        if (!viz[i]){
           conex++;
           DFS(i);
        }
    
    printf("%ld\n",conex);

return 0;
}