CareerCup

Hii i Found this question on glassdor. This question was asked in codenation.Can anyone tell how to solve this problem

procedure DFS(G, s, dest, g):
	let marked[1..G.V] keep track of the visited vertices
	call DFS_recursive(G, s, dest, marked, g)
end procedure

procedure DFS_recursive(G, u, dest, marked, pred, g):
	marked[u] = True
	if (u == dest) then:
		return True

	is_dest = False
	for each v such that gcd(u,v) < g:
		if marked[v] == False then:
			is_dest = DFS_recursive(G, u, dest, marked, pred, g)

	return is_dest

# for a pair (u,v) and for a value of g call: 
is_path = call DFS(G, u, v, g)

Note:
1. For gcd(a,b) you can use Euclid's algorithm.
2. If the value of g is the same for any (u,v) call then you can use some sort of dynamic programming (populate G.E as you go) for future queries!

It's Union find problem. construct connected components by doing this
:for all i if gcd(i,j)>g (both i,j belong to same component) where j is a multiple of i.Then you can check for any(u,v) if they can be reached(same component) or not.