Задать вопрос
@Xiran

Что не так с кодом, работающим с графом?

Алгоритм должен брать значение вершины графа, и если оно положительное, увеличивать значения всех смежных вершин на него самого:04628e18-afe2-d2a510415164.png
Я написал код:
#include <bitset>
#include <cstddef>
#include <functional>
#include <iostream>
#include <stack>
#include <vector>

constexpr std::size_t GRAPH_SIZE { 4 };

using Graph = std::vector<std::vector<std::size_t>>;
using ValuesTable = std::array<std::ptrdiff_t, GRAPH_SIZE>;
using Visited = std::bitset<GRAPH_SIZE>;
using WithAdj = std::function<void(std::size_t, std::size_t)>;

void dfs(Graph &graph, Visited &visited, WithAdj fn) {
    std::stack<std::size_t> stack;

    auto impl = [&stack, &graph, &visited, &fn](std::size_t vert) {
        stack.push(vert);

        while (!stack.empty()) {
            auto s = stack.top();
            stack.pop();

            if (!visited.test(s))
                visited.set(s);

            for (const auto &i : graph[s]) {
                fn(s, i);

                if (!visited.test(i))
                    stack.push(i);
            }
        }
    };

    for (std::size_t i { 0 }; i < GRAPH_SIZE; i++)
        impl(i);
}

int main() {
    Visited visited;

    Graph graph {
        { 1 }, { 0, 2 }, { 1, 0, 3 }, { 2 }
    };

    ValuesTable table {
        3, 2, -7, -13
    };

    auto fn = [&table](std::size_t self, std::size_t adj) {
        if (table[self] > 0)
            table[adj] += self;
    };

    dfs(graph, visited, fn);

    for (const auto &i : table)
        std::cout << i << " ";
}


Но он выводит 5 2 -5 -13, вместо 5 5 -2 -13.
  • Вопрос задан
  • 153 просмотра
Подписаться 1 Простой Комментировать
Решения вопроса 1
Alexandroppolus
@Alexandroppolus
кодир
Тебе не нужен dfs или bfs. Просто обойди циклом все вершины по массиву вершин, и для положительных увеличивай все соседние
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы