Cod sursa(job #2773257)

Utilizator ps2001Silviu Popescu ps2001 Data 5 septembrie 2021 22:30:05
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

typedef struct nod {
    int x;
    nod *a;
} *pNod;

pNod v[100005];

void add(pNod &dest, int val) {
    pNod p;
    p = new nod;
    p->x = val;
    p->a = dest;
    dest = p;
}

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;

        add(v[x], y);
        add(v[y], x);
    }

    vector<int> visit(n +1);

    function<void(int)> dfs = [&] (int node) {
        pNod p = v[node];
        visit[node] = 1;
        
        while (p != NULL) {
            if (visit[p->x] == 0)
                dfs(p->x);
            p = p->a;
        }
    };

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (visit[i] == 0) {
            cnt++;
            dfs(i);
        }
    }

    cout << cnt << '\n';
    return 0;
}