algorithm - 城市之间是否存在路径

Question

问题的链接是Q4 Traveling is Fun。

我只能想到一种蛮力方法来计算每个可能的 gcd 并从源到目的地运行 bfs 以检查是否存在路径。

但是上述方法在 5 个测试用例中给出了 TLE。谁能提供更有效的方法？

标签： algorithmdata-structuresgraph-theorygraph-algorithmgreatest-common-divisor

Answer 1

这是我将使用的图形结构的快速实现：

class GCDGraph {

    private Map<Integer, Set<Integer>> adj = new HashMap<>();

    public GCDGraph(int g, int[] srcCities, int[] dstCities){
        int n = srcCities.length;
        for(int i=0;i<n;i++){
            adj.put(i, new HashSet<>());
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                int gtmp = gcd(srcCities[i], dstCities[j]);
                if(gtmp > g){
                    adj.get(i).add(j);
                    adj.get(j).add(i);
                }
            }
            // we could add the connection i -> i (assuming srcCities[i] > g)
            // but that would not help us find a path, as it introduces a cycle
        }
    }

    private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

    public Set<Integer> adjacentVertices(int vertex){ return adj.get(vertex); }

    public int size(){ return adj.size(); }

    public boolean isEmpty(){ return size() == 0; }

    public boolean hasPath(int src, int dst){
        return buildPath(src, dst, new HashSet<>());
    }

    private boolean buildPath(int src, int dst, Set<Integer> tmp){
        if(src == dst){
            return true;
        } else {
            for(int nextVertex : adjacentVertices(src)){
                if(tmp.contains(nextVertex))
                    continue;
                tmp.add(nextVertex);
                if(buildPath(nextVertex, dst, tmp))
                    return true;
                tmp.remove(nextVertex);
            }
        }
        return false;
    }
}

它将邻接显式存储为 Map（允许快速查找）。
它有一些实用方法（size、isEmpty）。
它仅在构建时查找 GCD，并且对于每个 x/y 对仅查找一次。
并且它使用递归来执行BFS，尽快退出。