Here is the functional graph query implementation:
function planetsQueriesII(n, f, queries):
// Find cycles and label nodes
cycleId = array of size n, all -1
distToCycle = array of size n, all -1
cyclePos = array of size n, all -1
cycleLen = array of size n, all 0
visited = array of size n, all 0 // 0=unvisited, 1=in-progress, 2=done
function dfs(u, path):
if visited[u] == 2:
return
if visited[u] == 1:
// Found cycle
cycleStart = path.indexOf(u)
len = path.length - cycleStart
for i from cycleStart to path.length - 1:
v = path[i]
cycleId[v] = u
cyclePos[v] = i - cycleStart
cycleLen[v] = len
return
visited[u] = 1
path.append(u)
dfs(f[u], path)
visited[u] = 2
for i from 0 to n - 1:
if visited[i] == 0:
dfs(i, [])
// Compute distance to cycle for non-cycle nodes
// Build binary lifting table
up = 2D array of size n x LOG
for i from 0 to n - 1:
up[i][0] = f[i]
for j from 1 to LOG - 1:
for i from 0 to n - 1:
up[i][j] = up[up[i][j-1]][j-1]
function query(a, b):
// Check if b is reachable from a
// Case 1: Both in same tree branch
// Case 2: Both in same cycle
// Use binary lifting + cycle arithmetic
for (a, b) in queries:
print query(a, b)
Time: . Space: .