This unit covers the following
- Kruskal's algorithm
- Prim's algorithm
- Alternatives to the MST (maximum ST, minimax...)
Complementary notes can be found in section 4.3 of the book Competitive Programming 3.
- Unit 1: Complexity
- Unit 2: Linear data structures
- Unit 3: Sorting (basic idea, used in kruskal)
- Unit 4: Tree data structures (mainly heap)
- Unit 6: Graph representation
- Unit 7: Union find
- Unit 12: Greedy (basic idea, used in prim)
problems marked with (!) are recommended as beginning exercise
- (!) UVA 908 - Re-connecting Computer Sites
- UVA 11228 - Transportation system
- UVA 11631 - Dark roads
- UVA 11747 - Heavy Cycle Edges
- UVA 11857 - Driving Range
- UVA 10048 - Audiophobia
- UVA 544 - Heavy Cargo
- UVA 10369 - Arctic Network
- UVA 10600 - ACM contest and Blackout
- UVA 10462 - Is There A Second Way Left ?
- UVA 10147 - Highways