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

[Anonymous]

Я хотел решить эту проблему: НОД на ориентированном графе.
Я новичок в SCC, топологическом упорядочении, алгоритме Косаджару и т. д.
В целом я считаю, что чем больше узлов мы используем в пути, тем лучший результат может быть, потому что стоимость (НОД) никогда не будет расти. Вот мой подход к этой проблеме:

• Найдите все сильно связанные компоненты (поэтому я использую как можно больше узлов) и НОД (стоимость прохождения всего компонента). )
• Мы можем сопоставить найденные SCC с узлами и создать DAG, где один узел представляет весь SCC.

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

Код: Выделить всё

#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);
}
}

void top_sort_components(const vector& scc_g, vector& visited, stack& order, int node) {
visited[node] = true;

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

top_sort_components(scc_g, visited, order, node);
}

order.push(node);
}

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[i][0]].push_back(edges[i][1]);
rg[edges[i][1]].push_back(edges[i][0]);
}

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

for (int i = 1; i 

Подробнее здесь: [url]https://stackoverflow.com/questions/78212113/finding-path-with-smallest-gcd-of-nodess-weights-in-directed-graph[/url]