Draw a graph that contains 4 articulation points and 1 bridge.
Draw a graph that contains 3 strongly connected components.
Given the undirected graph in Figure 1, determine the values of the LOW function for every vertex, assuming a DFS starting at node A.
Given the directed graph in Figure 2, find out the topological order resulting with help of a DFS search.
Problem 1 (Articulation points and bridges) In a game, the user build cities and connects them with roads, while fighting a monster army. The monster army can either occcupy cities or distroy roads. Implement the algorithm that helps the monster deciding its next move - which city to occupy or which road to destroy. The monster wants to do the most damage to the user's territory, leaving it disconnected if possible.
Problem 2 ( Topological sorting ) The prerequisites between the courses of a degree program are given in a text file, where every line contains a course ID followed by the IDs of its prerequisites. Example: CS351 CS101 CS228 M121. Find a valid order of following all the courses of the degree program.