Examples of tasks in graphs

In this section, you will be able to get acquainted with applied problems that are solved using graphs. Some of the tasks have a structure, according to which it is enough just to choose the right algorithm and apply it to get an answer. The other part requires some modification of the original graph and a combination of several algorithms to solve. In any case, all the algorithms used are described in the theoretical part, which will help you to better understand the methods of solving problems.

Tasks

• Chain [dfs]
• Path [dfs]
• Gears [search wide]
• New Year's Party [maximum flow]
• Cubes [maximum flow]
• Game [max flow]
• Rope Telegraph [Minimum Span Tree (Prim's Algorithm)]
• Secret Pipes [Minimum Span Tree (Kruskal's algorithm)]
• Subway [minimum spanning tree (Prima algorithm), depth search]
• Network [minimal spar tree (Kruskal algorithm)]
• Olympiad in Alchemy [Dijkstra's algorithm]
• Walls [Floyd-Worshel algorithm]
• Blockade [Dijkstra's algorithm]

For each task, a detailed description of the solution method, a formal algorithm, an analysis of examples, a program listing and a compiled solution file are attached.