Cod sursa(job #2694120)

Utilizator teofilotopeniTeofil teofilotopeni Data 8 ianuarie 2021 09:22:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <vector>
using namespace std;

struct Nod {
    bool vizitat = false;
    vector <int> from;
};

void parcurge(int i, vector <Nod> *nodes) {
    (*nodes)[i].vizitat = true;
    for (int j = 0; j < (*nodes)[i].from.size(); j++)
        if (!(*nodes)[(*nodes)[i].from[j]].vizitat)
            parcurge((*nodes)[i].from[j], nodes);
}

int main() {
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    int n, m, x, y;
    scanf("%d %d", &n, &m);
    vector <Nod> nodes(n + 1);

    while (m--) {
        scanf("%d %d", &x, &y);
        nodes[x].from.push_back(y);
        nodes[y].from.push_back(x);
    }

    int total = 0;
    for (int i = 1; i <= n; total++) {
        parcurge(i, &nodes);
        while (i <= n && nodes[i].vizitat)
            i++;
    }
    printf("%d", total);
    return 0;
}