Hi Codeforces,

I'm going to IOI this year and I'm currently preparing for it. My teammates have recommended this site to me and I have registered here today. This site looks great so far :)

Anyway, back to the original topic. As graph theory is an important component in IOI, I'm currently preparing hard for it. I know that direct implementations of the standard graph algorithms will not be tested in IOI, so I'm trying to think of variations and applications of some standard algorithms. I have thought of these so far for MST and Dijkstra.

• MST

• Find number of unique MST

• Find MST that doesn't use a certain edge/certain edges
• Minimum Spanning Forest
• Second best spanning tree

• Dijkstra

• Find number of shortest paths
• Find shortest path with minimum/maximum/certain number of edges for a weighted graph
• Find shortest path that passes through a certain vertex/certain vertices/a certain edge/certain edges
• Second best shortest path

I would really appreciate it if anyone can help provide descriptions of possible solutions for the above variations. I would also appreciate it if anyone can state more variations of the common algorithms(not just these two) that I have not listed above.

Thank you!~