!!!Chapter 8 The Disjoint Set ADT_a relation r is defined on a set s. if for every e

Disjoint Set: 不相交集，并查集

8.1 Equivalence Relations

A relation R is defined on a set S if for every pair of elements (a, b), a, b ∈ S， a R b is either true or false. If a R b is true, then we say that a is related to b.

An equivalence relation is a relation R that satisfies three properties:

1. (Reflexive自反性) a R a, for all a ∈ S.

2. (Symmetric) a R b if and only if b R a.

3. (Transitive) a R b and b R c implies that a R c.

8.2 The Dynamic Equivalence Problem

Given an equivalence relation ~, the natural problem is to decide, for any a and b, if a ~ b.

The equivalence class（等价类） of an element a ∈ S is the subset of S that contains all the elements that are related to a.

The equivalence classes form a partition of S: every member of S appears in exactly one equivalence class.To decide if a ~ b, we need only to check whether a and b are in the same equivalence class.

The input is initially a collection of N sets, each with one element. This initial representation is that all relations (except reflexive relations) are false. Each set has a different element, so that Si ∩ Sj = ∅; this makes the setsdisjoint.

There are two permissible operations:

1. Find: returns the name of the set(The