Cod sursa(job #714475)

Utilizator Sm3USmeu Rares Sm3U Data 15 martie 2012 19:33:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <vector>
#define nMax 100001

using namespace std;

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

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);
    }
}

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

void rez()
{
    for (int i = 1; i <= n; ++ i){
        if (!viz[i]){
            componente ++;
            dfs (i);
        }
    }
}

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

    citire();
    rez();
    printf ("%d\n", componente);

    return 0;
}