Cod sursa(job #2237092)

Utilizator sorynsooSorin Soo sorynsoo Data 31 august 2018 16:15:25
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
using namespace std;

ifstream cin("dfs.in");
ofstream cout("dfs.out");

#define MAXN 100005

void dfs(int node, vector< vector<int> > const& graf, vector<bool> &used) {
    for(auto nextNode: graf[node]) {
        if(!used[nextNode]) {
            used[nextNode] = true;
            dfs(nextNode, graf, used);
        }
    }
}

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

    vector< vector<int> > graf(n + 5, vector<int>());
    vector<bool> used((unsigned  long) n, false);

    for(int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    int nrcpc = 0;
    for(int i = 1; i <= n; i++) {
        if(!used[i]) {
            nrcpc++;
            used[i] = true;
            dfs(i, graf, used);
        }
    }

    cout << nrcpc << "\n";

    return 0;
}