forked from phuang07/python_algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathunion_find.py
More file actions
110 lines (85 loc) · 3.41 KB
/
Copy pathunion_find.py
File metadata and controls
110 lines (85 loc) · 3.41 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""This module implements an union find or disjoint set data structure.
An union find data structure can keep track of a set of elements into a number
of disjoint (nonoverlapping) subsets. That is why it is also known as the
disjoint set data structure. Mainly two useful operations on such a data
structure can be performed. A *find* operation determines which subset a
particular element is in. This can be used for determining if two
elements are in the same subset. An *union* Join two subsets into a
single subset.
The complexity of these two operations depend on the particular implementation.
It is possible to achieve constant time (O(1)) for any one of those operations
while the operation is penalized. A balance between the complexities of these
two operations is desirable and achievable following two enhancements:
1. Using union by rank -- always attach the smaller tree to the root of the
larger tree.
2. Using path compression -- flattening the structure of the tree whenever
find is used on it.
complexity:
* find -- :math:`O(\\alpha(N))` where :math:`\\alpha(n)` is
`inverse ackerman function
<http://en.wikipedia.org/wiki/Ackermann_function#Inverse>`_.
* union -- :math:`O(\\alpha(N))` where :math:`\\alpha(n)` is
`inverse ackerman function
<http://en.wikipedia.org/wiki/Ackermann_function#Inverse>`_.
"""
class UF:
"""An implementation of union find data structure.
It uses weighted quick union by rank with path compression.
"""
def __init__(self, N):
"""Initialize an empty union find object with N items.
Args:
N: Number of items in the union find object.
"""
self._id = list(range(N))
self._count = N
self._rank = [0] * N
def find(self, p):
"""Find the set identifier for the item p."""
id = self._id
while p != id[p]:
id[p] = id[id[p]] # Path compression using halving.
p = id[p]
return p
def count(self):
"""Return the number of items."""
return self._count
def connected(self, p, q):
"""Check if the items p and q are on the same set or not."""
return self.find(p) == self.find(q)
def union(self, p, q):
"""Combine sets containing p and q into a single set."""
id = self._id
rank = self._rank
i = self.find(p)
j = self.find(q)
if i == j:
return
self._count -= 1
if rank[i] < rank[j]:
id[i] = j
elif rank[i] > rank[j]:
id[j] = i
else:
id[j] = i
rank[i] += 1
def __str__(self):
"""String representation of the union find object."""
return " ".join([str(x) for x in self._id])
def __repr__(self):
"""Representation of the union find object."""
return "UF(" + str(self) + ")"
if __name__ == "__main__":
print("Union find data structure.")
N = int(raw_input("Enter number of items: "))
uf = UF(N)
print("Enter a sequence of space separated pairs of integers: ")
while True:
try:
p, q = [int(x) for x in raw_input().split()]
uf.union(p, q)
except:
break
print(str(uf.count()) + " components: " + str(uf))