UVa 208

From Algorithmist
Jump to navigation Jump to search

208 - Firetruck[edit]

Summary[edit]

The problem is about finding all the paths between two vertices in a undirected graph.

Explanation[edit]

The problem can be solved through backtracking with pruning. Starting from vertex 1 (the fire station), the route is extended by one vertex at each step until the target vertex (the one on fire) is reached. Backtracking would give all available paths.

Two issues have to be handled. Let the current route be R and let u be the new vertex to be added into the route.

  • To avoid loops, make sure that u is not in R before R is extended to u.
  • If u does not lead to the target vertex, ignore it. That would save a lot of computing time. We can set up a "reachable" bitflag for each vertex by a BFS/DFS search starting from the target vertex.

Gotchas[edit]

Backtracking without pruning would lead to a TLE (Time Limit Exceeded).

Input[edit]

6
1 2
1 3
3 4
3 5
4 6
5 6
2 3
2 4
0 0
4
2 3
3 4
5 1
1 6
7 8
8 9
2 5
5 7
3 1
1 8
4 6
6 9
0 0

Output[edit]

CASE 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the firestation to streetcorner 6.
CASE 2:
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
There are 8 routes from the firestation to streetcorner 4.

References[edit]

'Programming Challenges: The Programming Contest Training Manual'