Поиск пути с наименьшим GCD веса узлов на направленном графике ⇐ C++

[Anonymous]

Я хотел решить эту проблему: GCD на направленном графике < /p>
Я новичок в SCC, топологическом упорядочении, алгоритме Косаджару и т. Д. < /p>
Как правило, я думаю, что чем больше узлов мы используем в пути, то лучший результат может быть, потому что стоимость (GCD) никогда не будет расти. Это мой подход к этой проблеме: < /p>

Найдите все тесно связанные компоненты (поэтому я использую как можно больше узлов) и GCD (стоимость пересечения всего компонента ). Снижение проблемы с поиском кратчайшего пути (от любого до любого узла) в взвешенном DGA. Но я понятия не имею, как я могу подойти к нему с приемлемой сложности времени. Вот как выглядит мой текущий код: < /p>
#include
#include
#include
#include

using namespace std;

int gcd(int a, int b) {
if (b == 0)
return a;

return gcd(b, a % b);
}

void top_sort(const vector& g, vector& visited, vector& order, int node) {
visited[node] = true;

for (const int ngbr : g[node]) {
if (visited[ngbr])
continue;

top_sort(g, visited, order, ngbr);
}

order.push_back(node);
}

void dfs_0(const vector& rg, const vector& c, vector& visited, vector& components_gcd, vector& components, int node, int component) {
visited[node] = true;
components_gcd[component] = gcd(components_gcd[component], c[node]);
components[node] = component;

for (const int ngbr : rg[node]) {
if (visited[ngbr])
continue;

dfs_0(rg, c, visited, components_gcd, components, ngbr, component);
}
}

int solve(int n, vector c, vector edges) {
vector g(n + 1, list());
vector rg(n + 1, list());
for (int i = 0; i < edges.size(); ++i) {
g[edges[0]].push_back(edges[1]);
rg[edges[1]].push_back(edges[0]);
}

vector visited(n + 1);
vector order;
order.reserve(n);

for (int i = 1; i
Прокомментируйте, если что -то неясно. Спасибо

Подробнее здесь: https://stackoverflow.com/questions/782 ... cted-graph