Practice: Disjoint sets
0 of 4 solved
About these problems
Apply, Connect, Reason and Stretch describe difficulty within this topic, not an official contest rating. Open any problem in any order; reading the chapter first is optional.
- 1Connection checksMaintain n initially separate vertices. Type 1 joins u and v. Type 2 asks whether u and v are currently connected through joins.ApplyNot started
- 2Growing networkAfter each undirected edge addition, print the number of connected components and the size of the largest component.ConnectNot started
- 3Redundant linksProcess undirected edges in input order. A link is redundant if its endpoints were already connected before adding it (including a self-loop). Count redundant links.ReasonNot started
- 4Least-cost backboneChoose edges connecting all n vertices with minimum total weight. Print -1 if connection is impossible. A one-vertex graph needs no edges and costs 0.StretchNot started