Data Structures and Algorithms Part I

Last Modified: 4/10/2025

2 Linked Lists

A linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.

In the implementation we use a sentinel code. Sentinel code make it easier to reason about code, and also give you specific goals to strive for in making sure your code works.

2.1 Singly Linked List

Singly linked lists contain nodes which have a value field as well as next field, which points to the next node in line of nodes.


97 collapsed lines
1
import java.util.Iterator;
2

3
public class SLList<T> implements Iterable<T> {
4

5
    /**
6
     * Node class for SLList
7
     */
8
    public static class Node<T> {
9
        public T item;
10
        public Node<T> next;
11

12
        public Node(T i, Node<T> n) {
13
            item = i;
14
            next = n;
15
        }
16
    }
17

18
    private final Node<T> sentinel;
19
    private int size;
20

21
    /**
22
     * Default Constructor for SLList
23
     */
24
    public SLList() {
25
        sentinel = new Node<>(null, null);
26
        size = 0;
27
    }
28

29
    /**
30
     * Constructor for SLList with one element
31
     *
32
     * @param x element to be added
33
     */
34
    public SLList(T x) {
35
        sentinel = new Node<>(null, null);
36
        sentinel.next = new Node<>(x, null);
37
        size = 1;
38
    }
39

40
    /**
41
     * Add element to the front of the list
42
     *
43
     * @param x element to be added
44
     */
45
    public void addFirst(T x) {
46
        sentinel.next = new Node<>(x, sentinel.next);
47
        size += 1;
48
    }
49

50
    /**
51
     * Add element to the end of the list
52
     *
53
     * @param x element to be added
54
     */
55
    public void addLast(T x) {
56
        size += 1;
57
        Node<T> p = sentinel;
58
        while (p.next != null) {
59
            p = p.next;
60
        }
61
        p.next = new Node<>(x, null);
62
    }
63

64
    /**
65
     * Return the size of the list
66
     *
67
     * @return size of the list
68
     */
69
    public int size() {
70
        return size;
71
    }
72

73
    /**
74
     * Iterator implementation for SLList
75
     */
76
    public Iterator<T> iterator() {
77
        return new SLListIterator();
78
    }
79

80
    private class SLListIterator implements Iterator<T> {
81
        private Node<T> p;
82

83
        public SLListIterator() {
84
            p = sentinel.next;
85
        }
86

87
        public boolean hasNext() {
88
            return p != null;
89
        }
90

91
        public T next() {
92
            T returnItem = p.item;
93
            p = p.next;
94
            return returnItem;
95
        }
96
    }
97
}


132 collapsed lines
1
#ifndef SLLIST_H
2
#define SLLIST_H
3

4
#include <iterator>
5

6
template <typename T>
7
class SLList {
8
public:
9
    template <typename U>
10
    struct Node {
11
        U item;
12
        Node* next;
13

14
        Node(U i, Node<U>* n) : item(i), next(n) {}
15
    };
16

17
private:
18
    Node<T>* sentinel;
19
    int size;
20

21
public:
22
    SLList();
23
    explicit SLList(T x);
24
    void addFirst(T x);
25
    void addLast(T x);
26
    [[nodiscard]] int getSize() const;
27
    class iterator;
28
    iterator begin();
29
    iterator end();
30
};
31

32
template <typename T>
33
class SLList<T>::iterator {
34
public:
35
    using iterator_category = std::forward_iterator_tag;
36
    using value_type = T;
37
    using difference_type = std::ptrdiff_t;
38
    using pointer = T*;
39
    using reference = T&;
40

41
private:
42
    Node<T>* current;
43

44
public:
45
    explicit iterator(Node<T>* node) : current(node) {}
46
    T& operator*() const;
47
    T* operator->() const;
48
    iterator& operator++();
49
    bool operator==(const iterator& other) const;
50
    bool operator!=(const iterator& other) const;
51
};
52

53
template <typename T>
54
SLList<T>::SLList() : sentinel(new Node<T>(T(), nullptr)), size(0) {}
55

56
template <typename T>
57
SLList<T>::SLList(T x) : sentinel(new Node<T>(T(), nullptr)), size(1) {
58
    sentinel->next = new Node<T>(x, nullptr);
59
}
60

61
/**
62
 * Add element to the front of the list
63
 */
64
template <typename T>
65
void SLList<T>::addFirst(T x) {
66
    sentinel->next = new Node<T>(x, sentinel->next);
67
    size++;
68
}
69

70
/**
71
 * Add element to the end of the list
72
 */
73
template <typename T>
74
void SLList<T>::addLast(T x) {
75
    size++;
76
    Node<T>* p = sentinel;
77
    while (p->next != nullptr) {
78
        p = p->next;
79
    }
80
    p->next = new Node<T>(x, nullptr);
81
}
82

83
/**
84
 * Return the size of the list
85
 */
86
template <typename T>
87
int SLList<T>::getSize() const {
88
    return size;
89
}
90

91
/**
92
 * Iterator implementation for SLList
93
 */
94
template <typename T>
95
typename SLList<T>::iterator SLList<T>::begin() {
96
    return iterator(sentinel->next);
97
}
98

99
template <typename T>
100
typename SLList<T>::iterator SLList<T>::end() {
101
    return iterator(nullptr);
102
}
103

104
template <typename T>
105
T& SLList<T>::iterator::operator*() const {
106
    return current->item;
107
}
108

109
template <typename T>
110
T* SLList<T>::iterator::operator->() const {
111
    return &(current->item);
112
}
113

114
template <typename T>
115
typename SLList<T>::iterator& SLList<T>::iterator::operator++() {
116
    if (current) {
117
        current = current->next;
118
    }
119
    return *this;
120
}
121

122
template <typename T>
123
bool SLList<T>::iterator::operator==(const iterator& other) const {
124
    return current == other.current;
125
}
126

127
template <typename T>
128
bool SLList<T>::iterator::operator!=(const iterator& other) const {
129
    return !(*this == other);
130
}
131

132
#endif // SLLIST_H


45 collapsed lines
1
class Node:
2
    """Represents a node in the singly linked list."""
3
    def __init__(self, item, next_node):
4
        """Initializes a Node with an item and the next node."""
5
        self.item = item
6
        self.next = next_node
7

8
class SLList:
9
    """Represents a singly linked list."""
10
    def __init__(self, x=None):
11
        """
12
        Initializes an SLList.
13
        If x is provided, initializes the list with one element x.
14
        Uses a sentinel node at the front.
15
        """
16
        self.sentinel = Node(None, None)
17
        self.size_val = 0
18

19
        if x is not None:
20
            self.sentinel.next = Node(x, None)
21
            self.size_val = 1
22

23
    def add_first(self, item):
24
        """Adds an item to the front of the list."""
25
        self.sentinel.next = Node(item, self.sentinel.next)
26
        self.size_val += 1
27

28
    def add_last(self, item):
29
        """Adds an item to the end of the list."""
30
        self.size_val += 1
31
        p = self.sentinel
32
        while p.next is not None:
33
            p = p.next
34
        p.next = Node(item, None)
35

36
    def size(self):
37
        """Returns the number of items in the list."""
38
        return self.size_val
39

40
    def __iter__(self):
41
        """Returns an iterator for the SLList."""
42
        p = self.sentinel.next
43
        while p is not None:
44
            yield p.item
45
            p = p.next

2.2 Doubly Linked List

While a deque defines the behavior (an interface) of a double-ended queue, a doubly linked list provides one way to realize that behavior through its design.


111 collapsed lines
1
import java.util.Iterator;
2

3
public class DLList<T> implements Iterable<T> {
4

5
    /**
6
     * Node class for DLList.
7
     * Each node holds a reference to its item and pointers to the previous and next
8
     * nodes.
9
     */
10
    private static class Node<T> {
11
        public T item;
12
        public Node<T> prev;
13
        public Node<T> next;
14

15
        public Node(T item, Node<T> prev, Node<T> next) {
16
            this.item = item;
17
            this.prev = prev;
18
            this.next = next;
19
        }
20
    }
21

22
    private final Node<T> sentinel;
23
    private int size;
24

25
    /**
26
     * Default constructor for an empty DLList.
27
     * A circular sentinel node is created where sentinel.next and sentinel.prev point to sentinel itself.
28
     */
29
    public DLList() {
30
        sentinel = new Node<>(null, null, null);
31
        sentinel.next = sentinel;
32
        sentinel.prev = sentinel;
33
        size = 0;
34
    }
35

36
    /**
37
     * Constructor for DLList with one element.
38
     *
39
     * @param x the element to be added
40
     */
41
    public DLList(T x) {
42
        sentinel = new Node<>(null, null, null);
43
        Node<T> newNode = new Node<>(x, sentinel, sentinel);
44
        sentinel.next = newNode;
45
        sentinel.prev = newNode;
46
        size = 1;
47
    }
48

49
    /**
50
     * Adds an element to the front of the list.
51
     *
52
     * @param x the element to be added
53
     */
54
    public void addFirst(T x) {
55
        Node<T> newNode = new Node<>(x, sentinel, sentinel.next);
56
        sentinel.next.prev = newNode;
57
        sentinel.next = newNode;
58
        size++;
59
    }
60

61
    /**
62
     * Adds an element to the end of the list.
63
     *
64
     * @param x the element to be added
65
     */
66
    public void addLast(T x) {
67
        Node<T> newNode = new Node<>(x, sentinel.prev, sentinel);
68
        sentinel.prev.next = newNode;
69
        sentinel.prev = newNode;
70
        size++;
71
    }
72

73
    /**
74
     * Returns the size of the list.
75
     *
76
     * @return the number of elements in the list
77
     */
78
    public int size() {
79
        return size;
80
    }
81

82
    /**
83
     * Provides an iterator over the list's elements.
84
     *
85
     * @return an iterator that traverses the list from front to back
86
     */
87
    @Override
88
    public Iterator<T> iterator() {
89
        return new DLListIterator();
90
    }
91

92
    private class DLListIterator implements Iterator<T> {
93
        private Node<T> current;
94

95
        public DLListIterator() {
96
            current = sentinel.next;
97
        }
98

99
        @Override
100
        public boolean hasNext() {
101
            return current != sentinel;
102
        }
103

104
        @Override
105
        public T next() {
106
            T returnItem = current.item;
107
            current = current.next;
108
            return returnItem;
109
        }
110
    }
111
}


156 collapsed lines
1
#ifndef DLLIST_H
2
#define DLLIST_H
3

4
#include <iterator>
5
#include <cstddef>
6

7
template <typename T>
8
class DLList {
9
public:
10
    template <typename U>
11
    struct Node {
12
        U item;
13
        Node* next;
14
        Node* prev;
15

16
        Node(U i, Node<U>* p, Node<U>* n) : item(i), next(n), prev(p) {}
17
    };
18

19
private:
20
    Node<T>* sentinel;
21
    int size;
22

23
public:
24
    DLList();
25
    explicit DLList(T x);
26
    void addFirst(T x);
27
    void addLast(T x);
28
    [[nodiscard]] int getSize() const;
29
    class iterator;
30
    iterator begin();
31
    iterator end();
32
};
33

34
template <typename T>
35
class DLList<T>::iterator {
36
public:
37
    using iterator_category = std::bidirectional_iterator_tag;
38
    using value_type = T;
39
    using difference_type = std::ptrdiff_t;
40
    using pointer = T*;
41
    using reference = T&;
42

43
private:
44
    Node<T>* current;
45

46
public:
47
    explicit iterator(Node<T>* node) : current(node) {}
48

49
    T& operator*() const;
50
    T* operator->() const;
51
    iterator& operator++();
52
    iterator& operator--();
53
    bool operator==(const iterator& other) const;
54
    bool operator!=(const iterator& other) const;
55
};
56

57
/**************************************
58
 * Implementation of the DLList class.*
59
 **************************************/
60

61
/* Default constructor: creates an empty list with a circular sentinel node. */
62
template <typename T>
63
DLList<T>::DLList() : size(0) {
64
    sentinel = new Node<T>(T(), nullptr, nullptr);
65
    sentinel->next = sentinel;
66
    sentinel->prev = sentinel;
67
}
68

69
/* Constructor with one element. */
70
template <typename T>
71
DLList<T>::DLList(T x) : size(1) {
72
    sentinel = new Node<T>(T(), nullptr, nullptr);
73
    sentinel->next = sentinel;
74
    sentinel->prev = sentinel;
75
    auto* newNode = new Node<T>(x, sentinel, sentinel);
76
    sentinel->next = newNode;
77
    sentinel->prev = newNode;
78
    newNode->next = sentinel;
79
    newNode->prev = sentinel;
80
}
81

82
/* Add element to the front of the list. */
83
template <typename T>
84
void DLList<T>::addFirst(T x) {
85
    auto* newNode = new Node<T>(x, sentinel, sentinel->next);
86
    sentinel->next->prev = newNode;
87
    sentinel->next = newNode;
88
    size++;
89
}
90

91
/* Add element to the end of the list. */
92
template <typename T>
93
void DLList<T>::addLast(T x) {
94
    auto* newNode = new Node<T>(x, sentinel->prev, sentinel);
95
    sentinel->prev->next = newNode;
96
    sentinel->prev = newNode;
97
    size++;
98
}
99

100
/* Return the size of the list. */
101
template <typename T>
102
int DLList<T>::getSize() const {
103
    return size;
104
}
105

106
/* Returns iterator to the first element. */
107
template <typename T>
108
typename DLList<T>::iterator DLList<T>::begin() {
109
    return iterator(sentinel->next);
110
}
111

112
/* Returns iterator to the end (sentinel node). */
113
template <typename T>
114
typename DLList<T>::iterator DLList<T>::end() {
115
    return iterator(sentinel);
116
}
117

118
/***************************
119
 * Iterator Implementation *
120
 ***************************/
121

122
template <typename T>
123
T& DLList<T>::iterator::operator*() const {
124
    return current->item;
125
}
126

127
template <typename T>
128
T* DLList<T>::iterator::operator->() const {
129
    return &(current->item);
130
}
131

132
/* Pre-increment: move to the next node. */
133
template <typename T>
134
typename DLList<T>::iterator& DLList<T>::iterator::operator++() {
135
    current = current->next;
136
    return *this;
137
}
138

139
/* Pre-decrement: move to the previous node. */
140
template <typename T>
141
typename DLList<T>::iterator& DLList<T>::iterator::operator--() {
142
    current = current->prev;
143
    return *this;
144
}
145

146
template <typename T>
147
bool DLList<T>::iterator::operator==(const iterator& other) const {
148
    return current == other.current;
149
}
150

151
template <typename T>
152
bool DLList<T>::iterator::operator!=(const iterator& other) const {
153
    return !(*this == other);
154
}
155

156
#endif  // DLLIST_H


45 collapsed lines
1
class DLList:
2
    class Node:
3
        def __init__(self, item, prev=None, next=None):
4
            self.item = item
5
            self.prev = prev
6
            self.next = next
7

8
    def __init__(self):
9
        # Create a circular sentinel node.
10
        self.sentinel = self.Node(None)
11
        self.sentinel.next = self.sentinel
12
        self.sentinel.prev = self.sentinel
13
        self.size = 0
14

15
    def addFirst(self, x):
16
        """Add an element to the front of the list."""
17
        new_node = self.Node(x, self.sentinel, self.sentinel.next)
18
        self.sentinel.next.prev = new_node
19
        self.sentinel.next = new_node
20
        self.size += 1
21

22
    def addLast(self, x):
23
        """Add an element to the end of the list."""
24
        new_node = self.Node(x, self.sentinel.prev, self.sentinel)
25
        self.sentinel.prev.next = new_node
26
        self.sentinel.prev = new_node
27
        self.size += 1
28

29
    def getSize(self):
30
        """Return the size of the list."""
31
        return self.size
32

33
    def __iter__(self):
34
        """Forward iterator: iterate from the first element to the end."""
35
        current = self.sentinel.next
36
        while current != self.sentinel:
37
            yield current.item
38
            current = current.next
39

40
    def iter_backward(self):
41
        """Backward iterator: iterate from the last element to the beginning."""
42
        current = self.sentinel.prev
43
        while current != self.sentinel:
44
            yield current.item
45
            current = current.prev

3 Union-Find (Disjoint Sets)

Union-Find data structure (also known as Disjoint-Set data structure), is a data structure that stores a collection of disjoint (non-overlapping) sets. It provides operations for adding new sets, merging sets (replacing them with their union), and finding a representative member of a set.

3.1 Quick Find (Eager Approach)

parent[i] is the root of $i$ , $p$ and $q$ are connected if and only if they have the same parent[i].
Find: Check if $p$ and $q$ have the same parent[i].
Union: To merge components containing $p$ and $q$ , change all entries whose id equals parent[p] to parent[q].

3.2 Quick Union (Lazy Approach)

parent[i] is the parent of $i$ , root of $i$ is parent[parent...[i]] (keep going until it doesn’t change)
Find: Check if $p$ and $q$ have the same root.
Union: To merge components containing $p$ and $q$ , set the id of $p$ ‘s root to the id of $q$ ‘s root.

3.3 Quick Union Improvements

For quick union, we can improve the algorithm by using weighted quick union and path compression (WQUPC).

Weighted quick-union: Keep track of size of each tree (number of objects), and balance it by linking root of smaller tree to root of larger tree, so that trees won’t be too tall.
Path compression: Change the pointer of this node to skip a level, closer to the root or directly point at the root. In this way, the tree will get flatter.

Propositions

Depth of any node $x$ is at most $\log_2 N$

Proof:

The depth of $x$ increase by $1$ when tree $T_1$ containing $x$ is merged into another tree $T_2$ . The size of the tree containing $x$ at least doubles since $|T_2| \geq |T_1|$ .

Therefore, the size of tree containing $x$ can double at most $\log_2 N$ times.
Starting from an empty data structure, any sequence of $M$ union-find ops on $N$ objects makes $\Theta \left(M \alpha \left(N\right) \right)$ array accesses.

The amortized time for any $m$ find or union operations on a disjoint-set forest containing $n$ objects is $O(m \log* n)$ , where $\log*$ denotes the iterated logarithm.
In theory, WQUPC is not quite linear, but in practice, it is linear.

In “cell-probe” model of computation, no linear-algorithm exists.


84 collapsed lines
1
import java.util.Scanner;
2

3
public class UF {
4

5
    private final int[] parent;  // parent[i] = parent of i
6
    private final byte[] rank;   // rank[i] = rank of subtree rooted at i (never more than 31)
7
    private int count;     // number of components
8

9
    /**
10
     * Initializes an empty union-find data structure with
11
     * {@code n} elements 0 through n-1.
12
     * Initially, each element is in its own set.
13
     *
14
     * @param n the number of elements
15
     * @throws IllegalArgumentException if {@code n < 0}
16
     */
17
    public UF(int n) {
18
        if (n < 0) throw new IllegalArgumentException("n must be non-negative");
19
        count = n;
20
        parent = new int[n];
21
        rank = new byte[n];
22
        for (int i = 0; i < n; i++) {
23
            parent[i] = i;
24
            rank[i] = 0;
25
        }
26
    }
27

28
    /**
29
     * Returns the canonical element (root) of the set containing element p.
30
     *
31
     * @param p an element
32
     * @return the canonical element of the set containing p
33
     * @throws IllegalArgumentException unless 0 <= p < n
34
     */
35
    public int find(int p) {
36
        validate(p);
37
        while (p != parent[p]) {
38
            parent[p] = parent[parent[p]]; // path compression
39
            p = parent[p];
40
        }
41
        return p;
42
    }
43

44
    /**
45
     * Returns the number of sets.
46
     *
47
     * @return the number of sets (between 1 and n)
48
     */
49
    public int count() {
50
        return count;
51
    }
52

53
    /**
54
     * Merges the set containing element p with the set containing element q.
55
     *
56
     * @param p one element
57
     * @param q the other element
58
     * @throws IllegalArgumentException unless 0 <= p < n and 0 <= q < n
59
     */
60
    public void union(int p, int q) {
61
        int rootP = find(p);
62
        int rootQ = find(q);
63
        if (rootP == rootQ) return;
64

65
        /* Weighted Quick Union: Make root of smaller rank point to root of larger rank. */
66
        if (rank[rootP] < rank[rootQ]) {
67
            parent[rootP] = rootQ;
68
        } else if (rank[rootP] > rank[rootQ]) {
69
            parent[rootQ] = rootP;
70
        } else {
71
            parent[rootQ] = rootP;
72
            rank[rootP]++;
73
        }
74
        count--;
75
    }
76

77
    // Validates that p is a valid index.
78
    private void validate(int p) {
79
        int n = parent.length;
80
        if (p < 0 || p >= n) {
81
            throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n - 1));
82
        }
83
    }
84
}


96 collapsed lines
1
#ifndef UF_H
2
#define UF_H
3

4
#include <vector>
5
#include <stdexcept>
6
#include <string>
7

8
/**
9
 * @brief The UnionFind class represents a union–find data type (disjoint sets).
10
 *
11
 * This implementation uses weighted quick union by rank with
12
 * path compression by halving.
13
 *
14
 * @tparam T The type used for indices (default is int).
15
 */
16
template <typename T = int>
17
class UnionFind {
18
private:
19
    std::vector<T> parent;  // parent[i] = parent of i
20
    std::vector<int> rank;  // rank[i] = rank of subtree rooted at i
21
    int count;              // number of components
22

23
    // Validate that p is a valid index.
24
    void validate(T p) const {
25
        if (p < 0 || p >= static_cast<T>(parent.size()))
26
            throw std::out_of_range("Index " + std::to_string(p) +
27
                                    " is not between 0 and " +
28
                                    std::to_string(parent.size() - 1));
29
    }
30

31
public:
32
    /**
33
     * @brief Constructs a union-find structure with n elements 0 ... n-1.
34
     *
35
     * @param n the number of elements
36
     * @throws std::invalid_argument if n is negative
37
     */
38
    explicit UnionFind(int n) : parent(n), rank(n, 0), count(n) {
39
        if (n < 0)
40
            throw std::invalid_argument("n must be non-negative");
41
        for (int i = 0; i < n; ++i)
42
            parent[i] = static_cast<T>(i);
43
    }
44

45
    /**
46
     * @brief Finds the canonical element (root) of the set containing p.
47
     *
48
     * Uses path compression by halving.
49
     *
50
     * @param p an element
51
     * @return the root of the set containing p
52
     * @throws std::out_of_range if p is not a valid index
53
     */
54
    T find(T p) {
55
        validate(p);
56
        while (p != parent[p]) {
57
            parent[p] = parent[parent[p]];  // path compression
58
            p = parent[p];
59
        }
60
        return p;
61
    }
62

63
    /**
64
     * @brief Merges the set containing element p with the set containing element q.
65
     *
66
     * @param p one element
67
     * @param q another element
68
     */
69
    void unionSets(T p, T q) {
70
        T rootP = find(p);
71
        T rootQ = find(q);
72
        if (rootP == rootQ) return;
73

74
        /* Weighted Quick Union: Make the tree with smaller rank point to the one with larger rank. */
75
        if (rank[rootP] < rank[rootQ])
76
            parent[rootP] = rootQ;
77
        else if (rank[rootP] > rank[rootQ])
78
            parent[rootQ] = rootP;
79
        else {
80
            parent[rootQ] = rootP;
81
            ++rank[rootP];
82
        }
83
        --count;
84
    }
85

86
    /**
87
     * @brief Returns the number of disjoint sets.
88
     *
89
     * @return the number of connected components
90
     */
91
    [[nodiscard]] int countSets() const {
92
        return count;
93
    }
94
};
95

96
#endif // UF_H


66 collapsed lines
1
class UnionFind:
2

3
    def __init__(self, n):
4
        """
5
        Initializes an empty union-find data structure with n elements 0 through n-1.
6
        Each element is initially in its own set.
7
        :param n: the number of elements (must be non-negative)
8
        :raises ValueError: if n is negative
9
        """
10
        if n < 0:
11
            raise ValueError("n must be non-negative")
12
        self.count = n
13
        self.parent = list(range(n))
14
        self.rank = [0] * n
15

16
    def _validate(self, p):
17
        """
18
        Validates that p is a valid index.
19
        :param p: an element index
20
        :raises ValueError: if p is not between 0 and n-1
21
        """
22
        n = len(self.parent)
23
        if p < 0 or p >= n:
24
            raise ValueError(f"Index {p} is not between 0 and {n - 1}")
25

26
    def find(self, p):
27
        """
28
        Returns the canonical element (root) of the set containing p.
29
        Implements path compression by halving.
30
        :param p: an element
31
        :return: the root of the set containing p
32
        """
33
        self._validate(p)
34
        while p != self.parent[p]:
35
            self.parent[p] = self.parent[self.parent[p]]  # path compression
36
            p = self.parent[p]
37
        return p
38

39
    def union(self, p, q):
40
        """
41
        Merges the set containing element p with the set containing element q.
42
        :param p: one element
43
        :param q: another element
44
        """
45
        rootp = self.find(p)
46
        rootq = self.find(q)
47
        if rootp == rootq:
48
            return
49

50
        # Make the tree with smaller rank point to the tree with larger rank.
51
        if self.rank[rootp] < self.rank[rootq]:
52
            self.parent[rootp] = rootq
53
        elif self.rank[rootp] > self.rank[rootq]:
54
            self.parent[rootq] = rootp
55
        else:
56
            self.parent[rootq] = rootp
57
            self.rank[rootp] += 1
58

59
        self.count -= 1
60

61
    def count_sets(self):
62
        """
63
        Returns the number of disjoint sets.
64
        :return: number of connected components
65
        """
66
        return self.count

Applications: Percoloation, games, dynamic connectivity, least common ancestor, Kruskal’s minimum spanning tree algorithm, etc.