Cod sursa(job #2604641)

Utilizator alex.ivan1105Ivan Alexandru alex.ivan1105 Data 23 aprilie 2020 02:05:00
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 100009

class Task {
public:
    void solve() {
        read_input();
        print_output(get_result());
    }

private:
    int n, m;

    vector<int> adj[NMAX];

    void read_input() {
        cin >> n >> m;

        for (int i = 1; i <= n; ++i) {
            int x, y;

            cin >> x >> y;

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

    void print_output(int ccNum) {
        cout << ccNum;
    }

    int get_result() {
       return do_dfs();
    }

    int do_dfs() {
        vector<int> used(n + 1);
        int ccNum = 0;
    
        for (int i = 1; i <= n; ++i) {
            if (!used[i]) {
                ccNum++;
                dfs(i, used);
            }
        }

        return ccNum;
    }

    void dfs(int& node, vector<int>& used) {
        used[node] = 1;
        // cout << node << " ";

        for (auto& it : adj[node]) {
            if (!used[it]) {
                dfs(it, used);
            }
        }
    }
};

int main() {
    // daca las linia asta citesc din fisier
    freopen("dfs.in",  "r", stdin); 

    // daca las linia asta afisez in fisier
    freopen("dfs.out", "w", stdout);

    Task *task = new Task();
    task->solve();
    delete task;

    return 0;
}