Cod sursa(job #1705394)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 20 mai 2016 15:10:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

bool ap[100010];
vector <int> v[100010];

inline void dfs (int nod)
{
    ap[nod] = true;
    for (auto &it : v[nod])
        if (!ap[it])
            dfs (it);
}

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

    int n, m;
    scanf ("%d %d", &n, &m);

    int rez = 0;
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        scanf ("%d %d", &x, &y);

        v[x].push_back (y);
        v[y].push_back (x);
    }

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

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

    return 0;
}