Determine whether a node is reachable
def computeGCD(x, y):



Just call it gcd. It's part of a computer program: you don't need to say that it computes.




    graph = {i+1:[] for i in range(n)}
    for i in originCities:
        for j in range(n):
            if i != j+1 and computeGCD(i, j+1) &gt; g:
                graph[i].append(j+1)



This is buggy: it doesn't build the whole graph. Consider test case connectedCities(16, 1, [14], [15]): there is a path 14 -- 6 -- 15 with GCDs respectively 2 and 3.

As a matter of style, I would find the code more readable if it iterated over range(1, n+1) and didn't have to continually increment the variable.




    for i in range(len(originCities)):
        paths = find_all_paths(graph, originCities[i], destinationCities[i])
        if len(paths) &gt; 0:
            res.append(1)
        else:
            res.append(0)



Spot the big performance problem: to determine whether any foo exists, it suffices to find one foo. You don't need to find every foo in the universe and then count them.

But just fixing that still leaves a smaller performance problem: if there are a lot of queries (i.e. if originCities and destinationCities are long) then it's quicker to do an expensive preprocessing to get an object which answers queries fast than it is to evaluate each query separately. As a big hint, in graph-theoretic terms the queries are "Are these two vertices in the same connected component?".

Note that if you really want to squeeze the asymptotic complexity (and it's not too bad for practical performance either), \$O(n \lg \lg n + q)\$ is achievable1 where \$q\$ is the number of queries.

1 Technically there's also a factor of \$\alpha(n)\$ where \$\alpha\$ is the inverse Ackermann function, but for practical purposes it's constant.