# scipy.cluster.hierarchy.DisjointSet¶

class scipy.cluster.hierarchy.DisjointSet(elements=None)[source]

Disjoint set data structure for incremental connectivity queries.

New in version 1.6.0.

Notes

This class implements the disjoint set , also known as the union-find or merge-find data structure. The find operation (implemented in `__getitem__`) implements the path halving variant. The merge method implements the merge by size variant.

References

1

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Examples

```>>> from scipy.cluster.hierarchy import DisjointSet
```

Initialize a disjoint set:

```>>> disjoint_set = DisjointSet([1, 2, 3, 'a', 'b'])
```

Merge some subsets:

```>>> disjoint_set.merge(1, 2)
True
>>> disjoint_set.merge(3, 'a')
True
>>> disjoint_set.merge('a', 'b')
True
>>> disjoint_set.merge('b', 'b')
False
```

Find root elements:

```>>> disjoint_set
1
>>> disjoint_set['b']
3
```

Test connectivity:

```>>> disjoint_set.connected(1, 2)
True
>>> disjoint_set.connected(1, 'b')
False
```

List elements in disjoint set:

```>>> list(disjoint_set)
[1, 2, 3, 'a', 'b']
```

Get the subset containing ‘a’:

```>>> disjoint_set.subset('a')
{'a', 3, 'b'}
```

Get all subsets in the disjoint set:

```>>> disjoint_set.subsets()
[{1, 2}, {'a', 3, 'b'}]
```
Attributes
n_subsetsint

The number of subsets.

Methods

 Add element x to disjoint set `merge`(x, y) Merge the subsets of x and y. `connected`(x, y) Test whether x and y are in the same subset. Get the subset containing x. Get all the subsets in the disjoint set. Find the root element of x.