The police department in the city of Fairfax has made all streets one-way. The m

Question

The police department in the city of Fairfax has made all streets one-way. The mayor claims that there is a way to drive legally from any intersection in the city to any other intersection and get back, but her claim has not been proved. A computer program is needed to determine whether the mayor is right. However, the city elections are coming up soon, and there is just enough time to run a linear-time algorithm. Formulate this problem graph-theoretically, and explain why it can indeed be solved in linear time Suppose it now turns out that the mayor's original claim is false. She next claims something weaker: if you start driving from town hall, navigating one-way streets, then no matter where you reach, there is always a way to drive legally back to the town hall. Formulate this weaker property as a graph-theoretic problem, and carefully show how it too can be checked in linear time.

Explanation / Answer

This can be solved in linear time using graph algorithms.

Basically you can assume major points of city as a node in a graph and basically we have to find out that whether all nodes are connected with each other or not.

This can be checked easily by using the Tarjan's strongly connected components algorithm which is linear in nature and is the best fir for the above problem.

It will take O(V+E) to solve the above problem

For second part also we can use the same algorithm to prove the same.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.