UVa 10000

Summary

Finding the longest path in a general graph is NP-Complete. However, since the graph we are given is a directed acyclic graph with a small N, we can use a relatively naive exhaustive search algorithm to solve this. Alternatively, we can use dynamic programming to solve this.

Exhaustive Search Explanation

We can use exhaustive search on the graph, since it's a directed acyclic graph. Recursion should suffice.

Exhaustive Search Optimizations

Store the best path from the start node to the all the nodes using linear space. Only branch if the current path is longer than the longest path to current node.

Dynamic Programming Explanation

Since the graph is acyclic, there is a topological ordering. Thus, we can topological sort the graph, and use dynamic programming on the following recurrence:

${\displaystyle f(x_{i})=max_{j:1\to N}(f(x_{j})+p(i,j))}$

where p(i,j) is is defined as 1 if there is a path from node i to node j, and 0 otherwise.

We can topological sort in ${\displaystyle O(V+E)}$ time, and the dynamic programming portion can be implemented trivially in ${\displaystyle O(V^{2})}$ time, or non-trivially in ${\displaystyle O(V\log V)}$ time.

Notes

• The input was increased, so optimization may or may not be necessary.

Gotchas

Print a new line after each test case.

Input

2
1
1 2
0 0
5
3
1 2
3 5
3 1
2 4
4 5
0 0
5
5
5 1
5 2
5 3
5 4
4 1
4 2
0 0
0


Output

Case 1: The longest path from 1 has length 1, finishing at 2.

Case 2: The longest path from 3 has length 4, finishing at 5.

Case 3: The longest path from 5 has length 2, finishing at 1.