Cod sursa(job #2193966)

Utilizator pakistanezuPopescu Alexandru Gabriel pakistanezu Data 11 aprilie 2018 20:48:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <vector>
#include <fstream>

#define NMAX 100001
std::ifstream f("dfs.in");
std::ofstream g("dfs.out");

class Task {
public:
    void solve() {
        read_input();
        g << get_result();
    }
private:
    int n, m;
    std::vector<int> adj[NMAX];

    void read_input() {
        f >> n >> m;
        int x, y;
        for (int i = 1; i <= m; ++i) {
            f >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
    }

    int get_result() {
        int count = 0;
        std::vector<bool> visited(n + 1, false);
        for (int i = 1; i <= n; ++i) {
            if (!visited[i]) {
                ++count;
                dfs(i, visited);
            }
        }
        return count;
    }

    void dfs(int node, std::vector<bool> &visited) {
        visited[node] = true;
        for (auto &v : adj[node]) {
            if (!visited[v]) {
                dfs(v, visited);
            }
        }
    }
};
int main() {
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}