Problem 2

You are given a map of Santorini, a hot destination for summer vacations in Greece. Looking at the map, you soon realize that all streets in the island are one-way. Before booking your tickets, you would like to know if you can still reach any point in the island from any other point.

1. Model this as a graph problem. What are the nodes and edges in the graph? How does the original question translate in graph language?

2. Design an algorithm to solve this problem in O(n + m) time. Prove the correctness and the running time of your algorithm.

3. Due to an unexpected surge of tourists, the local authorities decided to block some streets entirely in an effort to reduce traffic. This had the effect that it is not possible anymore to start at some point u and end back in u. Despite this authorities claim that it is possible to find a point S, so that starting in S you can visit all other points in Santorini exactly once. Design an algorithm to test this claim in time O(n + m). Prove the correctness and the running time of your algorithm.