Блог

Возникли проблемы с именем unordered_map с именем visited . Цель visited — отметить посещенные вершины в графе, которые являются парами char и int . Проблема в том, что значения в visited изменяются сами по себе, даже если я изменил их вручную после инициализации visited .

Я попробовал более простой способ объявить хэш для пары int и char, но это не сработало. Затем я попытался изменить пару char и int на int, умножив char на 1M и добавив int . Однако это тоже не сработало.

Подробности: когда функция BFS вызывается снова, вызывается тот же ключ (т.Е. Ключ представляет собой пару <‘c’, 1>, преобразованную в int) в условии:

if ( visited[(pair.first - '0')*1000000 pair.second] == 0 )

затем условие передается, даже если я ранее присвоил этому ключу значение 1.

 #include <vector>
#include <unordered_map>
#include <list>
#include <utility>

using namespace std;

typedef std::pair<char, int> p;

// define hash for pair<char, int>
struct pair_hash
{
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> amp;p) const
    {
        return std::hash<T1>()(p.first) ^ std::hash<T2>()(p.second);
    }
};



void BFS(pair<char, int> v, 
        unordered_map<int, int> visited, 
        unordered_map<pair<char, int>, vector<pair<char, int>>, pair_hash> graph)   {

    // Maybe int instead of a pair<char, int> as a key will work...
    int x = (v.first - '0')*1000000   v.second;
    if (visited[x] == 0) {

        // Create a queue for BFS
        list<pair<char, int>> queue;
    
        // Mark the current node as visited and enqueue it
        visited[x] = 1;
        queue.push_back(v);
    
        while(!queue.empty()) {
            // Dequeue a vertex from queue
            v = queue.front();
            queue.pop_front();

            // Get all adjacent vertices of the dequeued
            // vertex s. If a adjacent has not been visited,
            // then mark it visited and enqueue it
            for (p P : graph[v]) {
                int y = (P.first - '0')*1000000   P.second;

                // Problem lays here
                if (visited[y] == 0) {

                    // now I set converted pair<'c', 1> to int to 1:
                    visited[y] = 1;
                    // After 1, 2 calls of function named BFS the condtion
                    // if ( visited[ converted pair<'c', 1> to int ] == 0 )
                    // is passed even if I set it to 1 earlier


                    queue.push_back(P);
                }
            }
        }
    }
}
int main() {
        unordered_map<pair<char, int>, vector<pair<char, int>>, pair_hash> graph;


        // Container for marking vertices as visited
        unordered_map<int, int> visited;
        for (auto kv: graph) {
            int x = (kv.first.first - '0')*1000000   kv.first.second;
            visited[x] = 0;
        }


        // Graph traversal
        for (auto kv: graph) {
            BFS(kv.first, visited, graph);
        }
    }
    return 0;
}