Cod sursa(job #2606327)

Utilizator CristiPopaCristi Popa CristiPopa Data 27 aprilie 2020 15:43:37
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>
using namespace std;

const int kMod = 1e9 + 7;

class Node {
public:
    int nr;
    vector<Node*> neigh;
    Node(int x) {
        nr = x;
    }
    Node() {
        nr = -1;
    }
};

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

 private:
    int n;
    int m;
    vector<Node*> nodes;

    void read_input() {
        ifstream fin("dfs.in");
        fin >> n >> m;
        nodes.resize(n);
        for (int i = 0; i < m; ++i) {
            int x, y;
            fin >> x >> y;
            nodes[x]->nr = x;
            nodes[y]->nr = y;
            nodes[x]->neigh.push_back(nodes[y]);
            nodes[y]->neigh.push_back(nodes[x]);
        }
        fin.close();
    }

    int get_result() {
        int connected = 0;
        vector<bool> visited(n);
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                dfs(nodes[i], visited);
                ++connected;
            }
        }
        return connected;
    }

    void dfs(Node* node, vector<bool> &visited) {
        if (node->neigh.empty())
            return;
        visited[node->nr] = true;
        for (auto it : node->neigh) {
            if (!visited[it->nr])
                dfs(it, visited);
        }
    }
    void print_output(int result) {
        ofstream fout("dfs.out");
        fout << result << '\n';
        fout.close();
    }
};

// Please always keep this simple main function!
int main() {
    // Allocate a Task object on heap in order to be able to
    // declare huge static-allocated data structures inside the class.
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}