COMPSCI 61B Lecture 14: Disjoint Sets
Document Summary
The disjoint sets data structure has 2 operations: Isconnected(x,y): returns true if x and y are connected. Connections can be transitive, they don"t have to be direct. Force all items to be integers instead of arbitrary data. Declare the number of items in advance, everything is disconnected at start. Number of elements n can be huge. Number of method calls m can be huge. Calls to methods may be interspersed (can"t assume its only connect operations followed by onlyisconnected operations) Connecting 2 things: record every single connecting line in some data structure. But rather than manually writing out every single connecting line, only record the sets that each item belongs to. For each item, its connected component is the set of all items that are connected to that item - model connectedness in terms of sets. How things are connected isn"t something we need to know. Only need to keep track of which connected component each item belongs to.
