============================================================================
CSC 263 Tutorial 10 Winter 2019
============================================================================
1. Given a weighted connected undirected graph G = (V, E) with n vertices and m
edges, we define the Minimum Cycler of G as a set S of edges of minimum total
weight such that every cycle in G contains at least one edge in S. Devise an
algorithm that finds the Minimum Cycler in O(m logn) time, and justify its
correctness and runtime.
Hint: The algorithm can be described in one short sentence.
2. Consider the following new operation for disjoint sets.
- PRINT(x): print every element in S_x (the set containing x).
Explain how to augment the tree data structure for disjoint sets to
implement the PRINT operation. Your goal: achieve worst-case running
time O(|S_x|) for operation PRINT(x), without affecting the running time
of the other operations.
Write down each operation's detailed pseudo-code carefully.
You should first try to solve it by adding two additional attributes to each
node, then, as a challenge, think: can you achieve everything by adding only
one additional attribute?