Cod sursa(job #2434717)

Utilizator melutMelut Zaid melut Data 2 iulie 2019 13:52:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <string>
#include <vector>
#include <stack>

using namespace std;


string const inFile("dfs.in");
string const outFile("dfs.out");


ifstream _read(inFile);
ofstream _write(outFile);


void Read(unsigned &n, unsigned &m, vector<vector<unsigned>> &nodes) {
    _read >> n;
    _read >> m;

    nodes.resize(n);

    unsigned node1;
    unsigned node2;

    for (unsigned i = 0; i < m; ++i) {
        _read >> node1;
        _read >> node2;

        nodes[node1 - 1].push_back(node2 - 1);
        nodes[node2 - 1].push_back(node1 - 1);
    }
}


void DFS(vector<vector<unsigned>> const &nodes, vector<bool> &vis, unsigned const start) {
    stack<unsigned> _stack;
    unsigned node;
    bool found;

    _stack.push(start);

    while (_stack.empty() == false) {
        node = _stack.top();
        vis[node] = true;

        found = false;

        for (unsigned i = 0; i < nodes[node].size(); ++i) {
            if (vis[nodes[node][i]] == true) {
                continue;
            }

            _stack.push(nodes[node][i]);
            found = true;

            break;
        }

        if (found == false) {
            _stack.pop();
        }
    }
}


unsigned Count(vector<vector<unsigned>> &nodes) {
    unsigned _count = 0;
    vector<bool> vis(nodes.size(), false);

    for (unsigned i = 0; i < nodes.size(); ++i) {
        if (vis[i] == false) {
            DFS(nodes, vis, i);
            ++_count;
        }
    }

    return _count;
}


int main() {
    unsigned n;
    unsigned m;
    vector<vector<unsigned>> nodes;

    Read(n, m, nodes);

    _write << Count(nodes);

    return 0;
}