"meeting point" - help with faster algorithm
Hi.
My problem is to find the "meeting point" of two given vertices in directed graph. Every vertice in this graph has only one output edge, so there obviously could be some cycles. We have got for example graph which looks like this:
1->4
2->3
3->5
4->5
5->1
6->1
7->12
8->12
9->9
10->9
11->7
12->1
And we have to find the distance from the "meeting point" of two given vertices.
For example:
The first given vertice is 7 and second - 2. As we can see, the "meeting point" is for example 1, so the distance from 7 to 1 is 2, and from 2 to 1 - 3, so our output is "2 3".
There are also some restrictions: let the output be "x y", max(x,y) must be minimal, then min(x,y) must be also minimal, and if our output are still ambiguous, our x should be greater.
If x and y does not exist, we just write "-1 -1".
My solution is to run through the graph starting from the first given vertice (just like in DFS), saving the number of step in tab[number_of_vertice]. And the same for the second given vertice, but this time instead of saving the number, we check if tab[number_of_vertce] > 0. If true - we can write "tab[number_of_vertce] number_of_actual_step" and finish the algorithm.
But this is too slow for me, the number of vertices is 500 000, and the number of given pairs of vertices can also reach 500 000, so it looks like a linear-requested problem.
Could somebody help me with this problem?
Sorry for my English : )
