Cod sursa(job #861903)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 21 ianuarie 2013 23:38:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;

#define Nmax 100001

int N, M;
int a, b;
int nr = 0;

vector <int> Graf[Nmax];
bitset <Nmax> viz;

void citire(){

    freopen("dfs.in", "r", stdin);

    scanf("%d%d", &N, &M);

    for(; M; M--){

        scanf("%d%d", &a, &b);

        Graf[a].push_back(b);
        Graf[b].push_back(a);
    }
}

void dfs(int k){

    viz[k] = 1;

    vector <int> ::iterator it;

    for(it = Graf[k].begin(); it != Graf[k].end(); ++it)
        if(!viz[*it])
            dfs(*it);
}

void rezolva(){

    for(int i = 1; i <= N; i++)
        if(viz[i] == 0)
            nr++,
            dfs(i);
}

void afis(){

    freopen("dfs.out", "w", stdout);

    printf("%d\n", nr);
}

int main(){

    citire();
    rezolva();
    afis();

    return 0;
}