Cod sursa(job #146850)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 2 martie 2008 11:58:22
Problema Parcurgere DFS - componente conexe Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <vector>
#include <bitset>
#define nMax 131072

using namespace std;

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

void DFS(long x){
     viz[x]=1;
     for (long i=0;i<v[x].size();i++)
         if (!viz[v[x][i]])
            DFS(v[x][i]);
}

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<=n;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;
}