Cod sursa(job #798114)

Utilizator Sm3USmeu Rares Sm3U Data 15 octombrie 2012 19:22:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <vector>

#define nMax 100100

using namespace std;

int n;
vector <int> graf[nMax];
int viz[nMax];
int nrComponente;

void citire(){
    int m;
    scanf ("%d %d", &n, &m);
    while (m -- ){
        int x;
        int y;
        scanf ("%d %d", &x, &y);
        graf[x].push_back (y);
        graf[y].push_back (x);
    }
}

int dfs (int nod){
    viz[nod] = 1;
    for (unsigned int i = 0; i < graf[nod].size(); ++ i){
        if (viz[graf[nod][i]] == 0){
            dfs (graf[nod][i]);
        }
    }
}

void rezolvare(){
    for (int i = 1; i <= n; ++ i){
        if (viz[i] == 0){
            nrComponente ++;
            dfs (i);
        }
    }
}

void afisare(){
    printf ("%d\n", nrComponente);
}

int main()
{
    freopen ("dfs.in", "r", stdin);
    freopen ("dfs.out", "w", stdout);

    citire();
    rezolvare();
    afisare();

    return 0;
}