Путь существует между городами или нет - PullRequest
Новая
       45

Путь существует между городами или нет

0 голосов
/ 20 октября 2018

Ссылка на проблему: Q4 Путешествия - это весело .

Я могу думать только о грубой силе, чтобы вычислить каждый возможный gcd ​​и запустить bfs от источника до места назначения, чтобы проверить,существует путь или нет.

Но приведенный выше подход дает TLE в 5 тестовых случаях.Кто-нибудь может предложить более эффективный подход?

1 Ответ

0 голосов
/ 24 октября 2018

Это быстрая реализация структуры графа, которую я бы использовал: 

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 (допускает быстрый поиск).
Он имеет несколько служебных методов (размер,isEmpty).
Он ищет GCD только во время сборки и только один раз для каждой пары x / y.
И использует рекурсию для выполнения BFS, выходя из нее как можно скорее.

...