Graphs 0/61

Union-find (DSU): merging disjoint sets · 1 of 2

Union-find basics

Keep groups that only merge as trees in a parent array, and tell whether two elements are connected in a few steps with union by size and path compression.

4,026 words · 18 min read

Part 1 of 8 Union-find (DSU)

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 nn cities and no roads. Each day one new road opens between two different cities, for mm 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 nn and mm; each of the next mm lines holds the two cities of that day's road, numbered from 1.

Constraints

  • 1≤n≤1051 \le n \le 10^5
  • 1≤m≤2⋅1051 \le m \le 2 \cdot 10^5
  • 1≤a,b≤n1 \le a, b \le n

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, {1,2}\{1, 2\}, 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 mm roads. With n=105n = 10^5 cities and m=2×105m = 2 \times 10^5 roads, the largest input allowed, that is up to

(n+m)×m=300,000×200,000=6×1010 steps.(n + m) \times m = 300{,}000 \times 200{,}000 = 6 \times 10^{10} \text{ steps.}

Even at 10810^8 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.