Алгоритм должен брать значение вершины графа, и если оно положительное, увеличивать значения всех смежных вершин на него самого:
Я написал код:
#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.