Assuming I have a DAG and a given topological order function for every vertex v in the graph, when looking at 2 particular nodes: x, y which I know that |top(x)-top(y)|<10 how can I tell if adding the edge x->y will form a cycle in the graph? I'm trying to achieve a solution that is better then O(V+E)...
What I thought was just checking if top(x) > top (y), if it is then we created a cycle. But i'm afraid I might miss a case, also, does the fact that |top(x)-top(y)|<10 give me any additional info? any enlightments?
We can use the fact that |top(x) < top(y)| < 10
to find an efficient solution.
First, note that if top(x) < top(y)
there is no cycle. Otherwise, let ar[] = y, z₁, z₂ … z_k, x
be the nodes in the topological sort between y and x. If there is a path from y to x, it can only go through these vertices. So just check if there is a path:
haspath[] = {false}
haspath[1] = true
for i = 2 to k+2
for j = 1 to i-1
if haspath[j]==true and edge(ar[j],ar[i])
haspath[i] = true
break
There is a path from y to x iff haspath[k+2]
is true.