============================================================================
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?