Disjoint Sets The Disjoint Set data structure e Maintains a collection of disjoint sets o Each set has a representative member e Supports the following operations MAKE-SET(X): creates a new set containing X {x} x is also the representative 0y9·j UNION(x,y): unites the sets that contain x and y a X。V FIND-SET(x): returns a pointer to the representative of the set containing x Takes o(1) if each element has a pointer pointing to the representative CS3381 Des Anal of Alg(2001-2002 SemA) City Univ of HK /Dept of CS Helena Wong http://www.cs.cityu.edu.hk/-helena 6. Graph Algorithms-11CS3381 Des & Anal of Alg (2001-2002 SemA) City Univ of HK / Dept of CS / Helena Wong http://www.cs.cityu.edu.hk/~helena 6. Graph Algorithms - 11 Disjoint Sets The Disjoint Set data structure Maintains a collection of disjoint sets. {.,a,..} {.,y,..} {.,q,..} {.,a,..} {.,y,..} {.,q,..} {x} {.,a,..} {.,q,..} {..x,y,..} {.,a,..} {.,q,..} {..x,y,..} FIND-SET(x): returns a pointer to the representative of the set containing x. Each set has a representative member. Supports the following operations: MAKE-SET(x): creates a new set containing x. x is also the representative. UNION(x,y): unites the sets that contain x and y. Takes O(1) if each element has a pointer pointing to the representative