Вектор int, инициализированный с 0s при доступе, дает ненулевое значение

Question

Я написал простой алгоритм поиска нечетных циклов в графе. У меня есть посещенный вектор, который говорит мне, что если вектор был посещен, он инициализируется 0. 0. 1001 *

#include <iostream>
#include <vector>
#include <set>

#define UNVISITED 0
#define VISITED 1

using namespace std;

int vertices, edges;

vector<vector<int>> graph;
vector<int> visited;
vector<int> times;

int time_ = 1;
int hasOddCycle = false;

void dfs(int vertex) {
    if (visited.at(vertex) == VISITED)
        return;
    visited.at(vertex) = VISITED;
    times.at(vertex) = time_;
    time_++;

    for (auto elem: graph.at(vertex)) {
        if (visited.at(elem) == VISITED) {
            if (times.at(vertex) - times.at(elem) % 2 == 0)
                hasOddCycle = true;
        } else {
            dfs(elem);
        }
    }
}

int main() {
    cin >> vertices >> edges;

    for (int i = 0; i <= vertices; i++) {
        visited.emplace_back(UNVISITED);
        graph.emplace_back(vector<int>());
        times.push_back(0);
    }

    int from, to;
    for (int i = 0; i < edges; i++) {
        cin >> from >> to;
        graph.at(from).push_back(to);
        graph.at(to).push_back(from);
    }

    for (int i = 1; i <= vertices; i++) {
        dfs(i);
        if (hasOddCycle) {
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;

    return 0;
}

Когда я запускаю свой код с заданными данными, вызывается dfs (1) и устанавливает посещаемость от 1 до 0. Первый элемент в цикле dfs равен 2, поэтому я проверяю, была ли посещена вершина 2, и это дает мне истину безо всякой причины! !! Я понятия не имею, почему это ...

Входные данные (вершины, количество ребер и число вершин):

5 6
1 2
2 3
3 4
4 1
1 5
5 3

Answer 1

Ваша проверка посещений отключена, и глобальная переменная time_ затрудняет отслеживание. Поскольку вектор times предоставляет ту же информацию, что и вектор visited и , я удалил один visited. Каждый раз, когда вы вызываете dfs из main, счетчик посещенных времен для каждой вершины графа будет увеличиваться на единицу. Все они будут иметь одинаковое количество посещений, когда функция вернется. Вот альтернативный способ отслеживания посещений, который немного облегчает отслеживание:

#include <iostream>
#include <vector>
#include <set>

using namespace std; // bad practice

int vertices, edges;

vector<vector<int>> graph;
vector<int> times;

void dfs(int vertex) {
    static int indent = 1; // to indent recursion level in debug print

    int time_ = ++times.at(vertex);

    for (auto elem : graph.at(vertex)) {
        if (times.at(elem) != time_) {
            std::cout << std::string(indent, ' ') << "dfs(" << elem
                      << ") in graph @ vertex " << vertex << "\n";
            ++indent;
            dfs(elem);
            --indent;
        }
    }
}

int main() {
    cin >> vertices >> edges;

    times.resize(vertices+1);
    for (int i = 0; i <= vertices; i++) {
        graph.emplace_back(vector<int>());
    }

    int from, to;
    for (int i = 0; i < edges; i++) {
        cin >> from >> to;
        graph.at(from).push_back(to);
        graph.at(to).push_back(from);
    }

    for(int v=1; v<=vertices; ++v) {
    std::cout << "\nchecking graph from vertex " << v << "\n";
        dfs(v);
        for (int i = 1; i <= vertices; i++) {
            if (times[i] != v) {
                std::cout << " Error\n";
                return 0;
            }
        }
        std::cout << " all vertices has " << v << " visitation(s)\n";
    }

    return 0;
}

Выход:

checking graph from vertex 1
 dfs(2) in graph @ vertex 1
  dfs(3) in graph @ vertex 2
   dfs(4) in graph @ vertex 3
   dfs(5) in graph @ vertex 3
 all vertices has 1 visitation(s)

checking graph from vertex 2
 dfs(1) in graph @ vertex 2
  dfs(4) in graph @ vertex 1
   dfs(3) in graph @ vertex 4
    dfs(5) in graph @ vertex 3
 all vertices has 2 visitation(s)

checking graph from vertex 3
 dfs(2) in graph @ vertex 3
  dfs(1) in graph @ vertex 2
   dfs(4) in graph @ vertex 1
   dfs(5) in graph @ vertex 1
 all vertices has 3 visitation(s)

checking graph from vertex 4
 dfs(3) in graph @ vertex 4
  dfs(2) in graph @ vertex 3
   dfs(1) in graph @ vertex 2
    dfs(5) in graph @ vertex 1
 all vertices has 4 visitation(s)

checking graph from vertex 5
 dfs(1) in graph @ vertex 5
  dfs(2) in graph @ vertex 1
   dfs(3) in graph @ vertex 2
    dfs(4) in graph @ vertex 3
 all vertices has 5 visitation(s)