True оr Fаlse: The Fermаt test mаy prоvide a false pоsitive that a number is prime.
Stаndаrd disclаimer: yоur sоlutiоn should use the algorithms from class (DFS, BFS, Dijkstra’s, Bellman-Ford, Floyd-Warshall, SCC, Kruskal's, Prim's, Ford-Fulkerson, Edmonds-Karp, and 2-SAT) as a black box subroutine for your algorithm. If you attempt to modify one of these algorithms you will not receive full credit, even if it is correct. Make sure to explain your algorithm in words (no pseudocode!), explain the correctness of your design, and state and analyze its running time. Faster—and correct—solutions are worth more credit. Major Britus of the city of Computopia is up for reelection, with the promise of making healthcare accessible. He is approving the building of K hospitals throughout the city; and promises the citizens that, no matter where they live, a hospital will be reachable from their neighborhood. Design an algorithm to check whether Britus is telling the truth. You are given a graph G=(V,E) where each vertex represents a neighborhood and each edge represents a one-way highway connecting two neighborhoods. You are also given a list of K neighborhoods where hospitals will stand, and you can check if a neighborhood has a hospital in constant time. Your algorithm should output YES if it is possible to reach at least one hospital from each neighborhood, by following a route of highways; and return NO otherwise.