The components of a graph that grows
Union-find, also called a disjoint-set union (DSU), is a data structure that keeps a collection of elements divided into groups, with every element in exactly one group. It has two operations: find tells which group an element is in, and union merges two groups into one. Groups are never split. The structure suits a graph that receives its edges one at a time, where the groups are the connected components and each new edge may merge two of them.
A depth-first search counts the connected components of a graph that is given in full. In the first problem of this lesson the graph changes between one question and the next:
There are cities and no roads. Each day one new road opens between two different cities, for days. A component is a group of cities in which every city can reach every other one by road.
After each day, print two numbers: how many components there are, and how many cities the largest component has. The first input line holds and ; each of the next lines holds the two cities of that day's road, numbered from 1.
Constraints
Sample · Input
5 3 1 2 1 3 4 5
Output
4 2 3 3 2 3
In the sample the five cities start as five components of one city each. The road 1-2 joins two of them, which leaves 4 components, and the largest, , has 2 cities. The road 1-3 adds city 3 to that component, so there are 3 components and the largest has 3 cities. The last road, 4-5, joins the two cities that were still alone, and the answer for the third day is 2 components with a largest of 3.
We could answer each day by counting the components again with depth-first search, one search for every component. Such a count reads every city and every road built so far, and it has to be repeated after each of the roads. With cities and roads, the largest input allowed, that is up to
Even at steps a second that takes ten minutes, and the time limit is one second.
Nearly all of this work finds out again what was known the day before. A new road can change the components in one way only: if its two cities are in different components, those two become one, and if they are in the same component, nothing changes. So it is enough to keep the components stored from day to day, look up the components of the two cities when a road arrives, and merge them if they differ. Looking up and merging are the two operations of union-find, with the cities as its elements and the components as its groups.
Each group as a tree
Union-find stores each group as a tree. One element of the group is the root of the tree. Every other element has a link to another element of the group, its parent, and following the links from any element leads to the root. The links are kept in an array: parent[v] is the parent of , and for a root, which has no element above it, parent[v] is itself. The root stands for the whole group and is also called its representative.
The walk along the links is the operation find: find(v) starts at , follows the links until it reaches an element that is its own parent, and returns that root. Two elements are in the same group exactly when find returns the same root for both. The operation union merges two groups: union(a, b) finds the roots of and and, if they are different, makes one of them the parent of the other, which hangs one whole tree under the other root.
The Road Construction sample is too small to show much of this, because none of its trees gets deeper than one link. We follow the structure on six cities, numbered 0 to 5, and four roads that are built in the order 0-1, 2-3, 1-2, 0-3. At the start every city is a root, so parent[v] is . For each road we call union on its two cities, and for now union always hangs the second root under the first:
parent after each road, with the entry that the road changed highlighted. The numbers under the last row are the cities.The roads 0-1 and 2-3 each join two single cities. For the road 1-2, find(1) returns 0 and find(2) returns 2, so the root 2 is hung under the root 0, and city 3 comes into the group of city 0 with it, without being touched. For the road 0-3 both calls return 0. The two cities are in one group already, and the array stays as it is.
[0, 0, 0, 2, 4, 5] drawn as three trees. Each arrow points from to parent[v], and find(3) follows the highlighted arrows to the root 0.find(3) goes from 3 to its parent 2 and from 2 to 0, which is its own parent, so it returns 0. find(1) returns 0 as well, so 1 and 3 are in the same group, although neither is the parent of the other. Elements 4 and 5 are roots without children, and each is a group of its own.
A parent link is not a road. No road was built between cities 2 and 0, and yet parent[2] is 0. The array does not record which roads exist, only which cities belong together.
The two operations in code
In code, find is a loop that climbs until it reaches an element that is its own parent, and union is two calls of find and one assignment. The program builds the four roads and then compares two pairs of cities.
parent = [0, 1, 2, 3, 4, 5]
def find(v):
while parent[v] != v:
v = parent[v]
return v
def union(a, b):
a, b = find(a), find(b)
if a != b:
parent[b] = a
for a, b in [(0, 1), (2, 3), (1, 2), (0, 3)]:
union(a, b)
print(parent)
print(find(1) == find(3), find(1) == find(4))The program prints the array in the drawing, [0, 0, 0, 2, 4, 5], and then True False: cities 1 and 3 have the same root, and cities 1 and 4 have different roots.
The number of groups can be kept without looking at the trees. There are groups at the start, and a union that finds two different roots turns two groups into one. So a counter that starts at and goes down by 1 at each such union always holds the number of groups. On the six cities three roads joined different roots, which leaves groups.
The roots give the right answer after every road. At the start every city is its own root, and no road connects any two cities. A road between two cities with the same root connects nothing new, and union changes nothing. A road between two cities with different roots merges their two components and no others, and union merges their two trees and no others. So every road keeps the following true, from the start on: two cities have the same root exactly when the roads built so far connect them.
Union by size
A find follows one link for every level it climbs, so its cost is the depth of the element in its tree, and nothing so far keeps the trees shallow. Take the roads 1-0, 2-1, 3-2, 4-3 and 5-4 on six new cities. Each union hangs the second root under the first, and the result is one chain:
find(0) now follows 5 links. With cities the same kind of input builds a chain of links. Road Construction allows cities and roads, so an input can use its first 99,999 roads for the chain and give each of the other 100,001 roads city 0 as one end. Each of those roads calls find(0), and together they follow
which is hardly better than a search on every day.
The chain grew because each union hung the tree built so far, however large, under a single city. Union by size hangs the smaller tree under the larger one instead. We keep a second array size, in which size[r] is the number of elements in the tree with root . When union has found two different roots, it compares their sizes and hangs the root of the smaller tree under the root of the larger one. When the two trees are equally large either choice will do, and ours keeps the first root on top. The root that stays on top adds the size of the other tree to its own.
With this rule the same five roads give a different array. The road 1-0 joins two single cities and keeps 1 as the root. Every later road joins one more single city to the tree of root 1, which is the larger of the two, so the single city goes under 1:
size[1] is 6.Here no find follows more than one link. Other inputs make deeper trees, but the depth grows slowly. An element gets one link further from its root only when its tree is hung under another root, and the rule allows that only when the other tree is at least as large. So each time the depth of an element grows by 1, the tree it belongs to at least doubles in size. An element at depth is therefore in a tree of at least elements, and no tree has more than :
For cities, , so no find follows more than 16 links.
Path compression
Union by size limits how deep a tree can get. The second improvement makes a tree shallower every time it is used. When find(v) arrives at the root, it has passed a number of elements on the way, and it now knows the root of each of them. Path compression sets the parent of every element on that path to the root. The groups stay the same, because each of those elements had this root before and has it afterwards, and the next find from any of them follows a single link.
We try it on the chain from the previous part. A chain can only come about without union by size, but path compression works with either kind of union. find(0) climbs from 0 through 1, 2, 3 and 4 to the root 5, and then points 0, 1, 2 and 3 straight at 5:
The call itself still followed 5 links. The gain is in the calls after it, which follow one link from any city.
In a tree that is not a chain, the elements on the path take along whatever hangs below them. In the figure, find(4) passes 4, 3, 2 and 1 on its way to the root 0:
find(4). Elements 5 and 6 were not on the path, but they hang from elements that were.Element 5 was three links from the root before the call and is two links from it afterwards, although find(4) never visited it.
Path compression in code
In code, find gets a second loop. The first loop climbs to the root as before. The second starts at again, walks the same path, and sets each parent to the root as it goes:
parent = [1, 2, 3, 4, 5, 5]
def find(v):
root = v
while parent[root] != root: # first loop: climb to the root
root = parent[root]
while parent[v] != root: # second loop: point the path at the root
above = parent[v]
parent[v] = root
v = above
return root
print(find(0))
print(parent)Run on the chain, the program prints the root 5 and then the array of the second row above.
The USACO Guide and cp-algorithms write find as a short recursive function, which compresses the path as its calls return. In Python that form depends on union by size: without it, a chain of 1,000 elements already goes over Python's default limit of 1,000 nested calls. The programs in this lesson use the two loops.
Try both rules
The widget holds six cities, and both rules start switched off. The first button adds the roads of our example one at a time, 0-1, 2-3, 1-2 and 0-3, and the drawing and the table show the trees and the array parent after each.
Build a chain adds the roads 1-0, 2-1 and so on up to 5-4, and the tallest tree then has height 5, which means that its deepest city is 5 links from the root. With Union by size switched on, the same button builds a tree of height 1. To see path compression, switch Union by size off and Path compression on, build the chain, leave at 0 and press Find the root of a. The links that the call rewrites are drawn in green.
The structure with both rules
With both rules the structure is a class of about twenty-five lines. It keeps the arrays parent and size and a counter components, and its union returns whether it merged two groups, which the programs below use. The lines after the class solve Road Construction:
input = sys.stdin.readline
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
self.components = n
def find(self, v):
root = v
while self.parent[root] != root:
root = self.parent[root]
while self.parent[v] != root: # path compression
above = self.parent[v]
self.parent[v] = root
v = above
return root
def union(self, a, b):
a, b = self.find(a), self.find(b)
if a == b:
return False
if self.size[a] < self.size[b]: # union by size
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
self.components -= 1
return True
n, m = map(int, input().split())
dsu = DSU(n)
largest = 1
out = []
for _ in range(m):
a, b = map(int, input().split())
if dsu.union(a - 1, b - 1):
largest = max(largest, dsu.size[dsu.find(a - 1)])
out.append(f"{dsu.components} {largest}")
print("\n".join(out))On the sample the program prints 4 2, 3 3 and 2 3. The cities are numbered from 1 in the input and from 0 in the arrays, which is why it subtracts 1 from each.
The largest component can only change on a day when two components merge, so the program looks at a size only after a union that returned true. It reads size at the root that find returns, because size is kept up to date only for roots. The entry of an element that was hung under another root still holds the size its tree had at that moment.
Each road costs two calls of find inside union, and a third one when the road merges two components. With union by size none of them climbs more than 16 links, so for the largest input the calls climb at most
while a search on every day took up to steps. Path compression lowers the number further.
Worked example
Step through the roads
The trace runs this structure on the six cities and the four roads of our example and shows parent, size and the root of every city after each road. One step differs from the run we followed by hand. The last road, 0-3, looks up the root of city 3 by way of city 2, and path compression then points 3 straight at 0.
The other presets are a road that is given twice, a single city that joins a tree of three, and the sample of Road Construction with its cities numbered from 0.
Each vertex begins as the root of its own one-vertex tree, so there are n components. Same root means same component.
- components
- 6
Change the example input
Current result: 3
Cost of the operations
- `find` or `union`, with union by size
- An element is at most links from its root.
- The same with path compression added
on average over a run - is the inverse Ackermann function, which is at most 4 for any a computer can hold. A single
findcan still follow links. - Memory
- Two arrays of entries, however many edges arrive.
- A search after every edge
- Each search reads the whole graph again.
Union-find is the right tool when edges arrive over time and the questions in between ask whether two vertices are connected, how many components there are or how large one of them is. For a graph that is given in full and does not change, a depth-first search finds every component in time, and union-find gains nothing over it.
Two things are outside its reach. It cannot remove an edge, because the trees do not record which edges built them. And it pays no attention to the direction of an edge, so it cannot tell which vertices can be reached from which in a directed graph.
Edges that close a cycle
When union returns false, its two elements had the same root already, so a path of earlier edges joins them. The new edge and that path together form a cycle. This gives a second test for a cycle in an undirected graph, besides a depth-first search: add the edges one at a time, and the graph has a cycle exactly when some union returns false. The test also tells which edge completed the cycle, and the next problem asks for that edge:
A tree on vertices to had one extra edge added between two vertices that were not already adjacent. You get the resulting edges in a list.
Return an edge whose removal leaves a tree on all vertices. If several edges qualify, return the one that appears last in the list.
Constraints
edges.length- No repeated edges; the graph is connected
Sample 1 · Input
edges = [[1,2],[1,3],[2,3]]
Output
[2,3]
Sample 2 · Input
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output
[1,4]
A tree with one extra edge has exactly one cycle, and removing any edge of that cycle leaves a tree again. Of those edges the problem wants the one that comes last in the list. We add the edges in the order of the list. As long as some edge of the cycle is still missing, the edges added so far contain no cycle and every union returns true. The first union that returns false therefore belongs to the last edge of the cycle, and that edge is the answer.
In the second sample the edges 1-2, 2-3 and 3-4 each join two groups. Then 1 and 4 have the same root, so the answer is [1, 4]. The edge 1-5 is not read at all.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, v):
root = v
while self.parent[root] != root:
root = self.parent[root]
while self.parent[v] != root: # path compression
above = self.parent[v]
self.parent[v] = root
v = above
return root
def union(self, a, b):
a, b = self.find(a), self.find(b)
if a == b:
return False
if self.size[a] < self.size[b]: # union by size
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
return True
def find_redundant_connection(edges):
dsu = DSU(len(edges) + 1) # vertices start at 1; entry 0 is unused
for a, b in edges:
if not dsu.union(a, b):
return [a, b]
return []
print(find_redundant_connection([[1, 2], [1, 3], [2, 3]]))
print(find_redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]))The class DSU is the one from the previous part without the counter. The graph has as many edges as vertices, since a tree on vertices has edges and one was added, so len(edges) is . The arrays get one entry more than that, because the vertices are numbered from 1 and entry 0 stays unused.
Elements that are not vertices
The elements of a union-find structure do not have to be the vertices of a graph. Anything that falls into groups through statements of the form "these two belong together" can be merged in the same way, once each thing has a number from 0 to that serves as its index in the arrays. In the next problem the things are email addresses:
Each account is a list whose first entry is a name and whose other entries are emails. Two accounts belong to the same person when they share an email, and this chains: if A shares an email with B and B with C, all three are one person. Two different people can have the same name.
Return one account per person: the name, then all of that person's emails in sorted order. The accounts can be returned in any order.
Constraints
-
accounts.length - Each account has a name and 1 to 9 emails
- Each email has at most 30 characters
Sample · Input
accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output
[["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
In the sample the first two accounts both contain johnsmith@mail.com, so they belong to one person, who has three addresses in all. The last account shares no address with any other, so its John is a different person, and Mary is a third.
We make every distinct address an element. A hash map gives each address a number in the order in which the addresses first appear, and we also keep the name of the account in which each one first appeared. All addresses of one account belong to one person, so for each account we call union on its first address and each of its other addresses. After that, two addresses have the same root exactly when they belong to the same person. We collect the addresses by root, sort each group and put the name in front.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, v):
root = v
while self.parent[root] != root:
root = self.parent[root]
while self.parent[v] != root: # path compression
above = self.parent[v]
self.parent[v] = root
v = above
return root
def union(self, a, b):
a, b = self.find(a), self.find(b)
if a == b:
return False
if self.size[a] < self.size[b]: # union by size
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
return True
def accounts_merge(accounts):
email_id, name_of = {}, {}
for account in accounts:
for email in account[1:]:
if email not in email_id:
email_id[email] = len(email_id) # the next free number
name_of[email] = account[0]
dsu = DSU(len(email_id))
for account in accounts:
first = email_id[account[1]]
for email in account[2:]:
dsu.union(first, email_id[email])
groups = {} # root -> addresses of that person
for email, i in email_id.items():
groups.setdefault(dsu.find(i), []).append(email)
return [[name_of[emails[0]]] + sorted(emails) for emails in groups.values()]
accounts = [["John", "johnsmith@mail.com", "john_newyork@mail.com"],
["John", "johnsmith@mail.com", "john00@mail.com"],
["Mary", "mary@mail.com"],
["John", "johnnybravo@mail.com"]]
for account in accounts_merge(accounts):
print(" ".join(account))The program prints one line for each person of the sample, the name followed by the sorted addresses. With at most 1,000 accounts of at most 9 addresses there are at most 9,000 elements, so the unions take very little time, and sorting the groups is the larger part of the work.
Common union-find mistakes
Linking the elements instead of their roots:
parent[a] = b.- Where it breaks
- With
n = 3and the edges 0-1 and then 0-2, the second union moves 0 from under 1 to under 2. Nowfind(1)is 1 andfind(2)is 2, so 1 and 2 look disconnected although the path 1, 0, 2 joins them. - The fix
- Find both roots first, and set the parent of one root to the other.
Comparing parents instead of roots.
- Where it breaks
- With
n = 4and the edges 0-1, 2-3 and 1-3, union by size leavesparent = [0, 0, 0, 2].parent[1]is 0 andparent[3]is 2, so the comparison says that 1 and 3 are apart, although they are connected. - The fix
- Compare
find(a)withfind(b).
Lowering the count of components at every edge.
- Where it breaks
- With
n = 3and the edge 0-1 given twice, the count goes down to 1. There are 2 components, because the second copy of the edge joins nothing. - The fix
- Lower the count only when the two roots differ.
Reading
size[v]for an element that is not a root.- Where it breaks
- With
n = 3and the edges 0-1 and 0-2, the arrays end asparent = [0, 0, 0]andsize = [3, 1, 1].size[1]is 1, although the group of element 1 has 3 elements. - The fix
- Read
size[find(v)].
Using union-find to look for a cycle in a directed graph.
- Where it breaks
- The edges
0 → 1,0 → 2and1 → 2contain no directed cycle. Union-find finds both ends of the last edge in one group and reports a cycle. - The fix
- For directed graphs use a depth-first search that marks the vertices on the current path, as on the Cycle detection page.
Recall A network of 6 computers, numbered 0 to 5, has the cables 0-1, 0-2, 0-3, 1-2 and 1-3, and we call `union` for each cable in that order. How many calls return false, how many components are left, and how many cables have to be unplugged and moved to connect all six computers?
Two calls return false, the ones for 1-2 and 1-3: after the first three cables the computers 0, 1, 2 and 3 have the same root. Computers 4 and 5 have no cable, so 3 components are left. Joining 3 components takes 2 new connections, one fewer than the number of components. The two cables for which union returned false each lie on a cycle and can be unplugged without disconnecting anything, so 2 moves are enough.