有向图节点权值最小GCD路径求解：SCC转DAG后处理疑问

背景与初步思路 #

我正在解决HackerEarth上的《有向图上的GCD》问题，刚接触SCC（强连通分量）、拓扑排序、Kosaraju算法这类技术。我认为路径包含的节点越多结果越好，因为GCD（最大公约数）不会增大。我的思路是：

• 找出所有SCC并计算每个分量的GCD；
• 将SCC映射为节点构建DAG（有向无环图）。

此时问题转化为在带权DAG中求解任意两点间的最小GCD路径，但我不知道如何以可接受的时间复杂度实现。

当前实现代码 #

#include <iostream>
#include <vector>
#include <list>
#include <stack>

using namespace std;

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

    return gcd(b, a % b);
}

void top_sort(const vector<list<int>>& g, vector<bool>& visited, vector<int>& 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<list<int>>& rg, const vector<int>& c, vector<bool>& visited, vector<int>& components_gcd, vector<int>& 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<int> c, vector<vector<int>> edges) {
    vector<list<int>> g(n + 1, list<int>());
    vector<list<int>> rg(n + 1, list<int>());
    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<bool> visited(n + 1);
    vector<int> order;
    order.reserve(n);

    for (int i = 1; i <= n; ++i) {
        if (!visited[i])
            top_sort(g, visited, order, i);
    }

    reverse(order.begin(), order.end());
    fill(visited.begin(), visited.end(), false);

    vector<int> components_gcd(n + 1);
    vector<int> components(n + 1);
    int component = 0;
    for (const int node : order) {
        if (!visited[node]) {
            ++component;
            dfs_0(rg, c, visited, components_gcd, components, node, component);
        }
    }

    vector<list<int>> scc_g(component, list<int>());
    for (int i = 0; i < edges.size(); ++i) {
        if (components[edges[i][0]] != components[edges[i][1]]) {
            scc_g[components[edges[i][0]]].push_back(components[edges[i][1]]);
        }
    }

    // I struggle here. scc_g is our DAG with SCCs as single nodes
}

困惑点 #

代码已经完成了SCC的提取和DAG的构建，但在注释标注的位置，不知道如何继续实现带权DAG中任意两点间最小GCD路径的求解，同时保证时间复杂度在可接受范围内。

若有不清楚的地方请告知，感谢帮助。

内容的提问来源于stack exchange，提问作者Szyszka947