Disjoint Set Union (DSU) Part 2 - Preparation to IOI Part 3
Module 2: DSU
Disjoint Set Union (DSU) Part 2
Disjoint Set Union (DSU) Part 2
Назария
Дарси 2 аз 4
Хониш: 24 дақиқа
Introduction
DSU is usually introduced as a data structure for connected components. It answers questions like: are two vertices already in the same component, and what happens if we add an edge between them?
But DSU can do more than just connectivity. Sometimes, each component has extra information attached to it. In this lecture, we will solve a more interesting problem: edges are added one by one, and after every added edge we must know whether the graph is still bipartite.
A graph is bipartite if we can color every vertex with two colors, for example color 0 and color 1, so that every edge connects vertices of different colors. The important idea is that DSU can store not only the leader of each component, but also the relation between a vertex and its leader.
By the end of this lecture, students should understand how to store extra information on the DSU tree and how to use it while merging components.
Problem or motivation
We have n vertices and no edges at the beginning. Then q edges are added one by one.
After each added edge (u,v), print:
YES if the whole graph is still bipartite.
NO if the graph is no longer bipartite.
Once the graph becomes not bipartite, it will stay not bipartite, because we only add edges and never remove them.
For example, if we add edges and then the third edge creates a triangle. A triangle has odd length, so it cannot be bipartite.
The simplest idea is to rebuild the answer after every new edge.
After adding an edge, we can run the normal bipartite check from graph theory:
Clear all colors.
Start BFS or DFS from every unvisited vertex.
Give the start vertex color 0.
Every time we go through an edge, give the neighbor the opposite color.
If we ever see an edge where both endpoints already have the same color, the graph is not bipartite.
This is correct, but it repeats too much work. If we already checked the graph after the first 1000 edges, and then one more edge is added, we do not want to color the whole graph again from zero.
For one check, BFS or DFS takes O(n+m). If we do this after every edge, the total time can become O(q(n+q)), which is too slow for large constraints.
So we need a way to update the answer when a new edge appears, without rebuilding all colors from scratch.
Core concept
For a normal DSU, every vertex points to a parent, and the root of the tree represents the whole component.
For this problem, connectivity alone is not enough. We also need to know whether two vertices should have the same color or different colors inside their component.
The key idea is to store one more value:
parent[x] — parent of vertex x in the DSU tree.
size[x] — size of the component if x is a root.
parity[x] — whether x has the same color as its parent or a different color.
bipartite[x] — whether the component is still bipartite if x is a root.
Here parity[x] is either 0 or 1:
0 means x has the same color as parent[x].
1 means x has the opposite color from parent[x].
When we call find_set(x), we want two things:
The root of the component.
The parity of x compared to that root.
If two vertices have the same root, then their parities to the root tell us their relation:
If their parities are equal, they have the same color.
If their parities are different, they have different colors.
This is exactly what we need for bipartite checking, because every new edge requires its endpoints to have different colors.
Main algorithm
When we add a new edge (x,y), there are two cases.
First, suppose x and y are already in the same component. Then DSU already knows their current color relation. Because the new edge requires them to be different:
If x and y already have different parity, the edge is fine.
If x and y have the same parity, this edge connects two vertices of the same color. That creates an odd cycle, so the component is no longer bipartite.
Second, suppose x and y are in different components. Then there is no conflict yet, because we are connecting two separate colorings. We can flip one whole component if needed. In DSU terms, this means we choose the parity of the root that gets attached.
Let:
X be the root of x.
Y be the root of y.
px be the parity of x to X.
py be the parity of y to Y.
When we attach root X under root Y, we must set parity[X] so that x and y become different colors. The required value is:
parity[X] = px xor py xor 1
The final 1 appears because an edge requires different colors.
We also merge the bipartite flags. If one of the two components was already bad, the merged component is also bad.
Algorithm:
Why does union by size help? When we attach one DSU tree under another, we always attach the smaller component under the larger component. So if the parent of some vertex changes because its component was attached, the size of the component containing that vertex at least doubles. A component can double only about logn times before it reaches size n. Therefore, without path compression, the height is O(logn) and each operation is O(logn).
Path compression makes it even faster in practice and in theory. After find_set(x), the vertex points directly to the root, and its parity is also updated directly to the root. With union by size and path compression together, DSU operations are almost constant time.
Mental model and detailed walkthrough
The easiest way to understand this version of DSU is to stop thinking about exact colors like “red” and “blue”. Instead, think about colors relative to the root.
Inside one DSU component:
c=0 means the vertex has the same imagined color as the root.
c=1 means the vertex has the opposite imagined color from the root.
An edge label 1 in the DSU tree means “different from parent”.
An edge label 0 means “same as parent”.
We will use a simpler example than before:
Add (1,2)
Add (2,3)
Add (3,4)
Add (4,1)
These four edges form a square, which is bipartite. Then we add:
Add (1,3)
This last edge adds a diagonal inside the square and creates triangle 1-2-3-1, so the graph becomes not bipartite.
In the TracePlayer below, the first graph is the real graph. The second graph is the DSU parity view: vertices are placed by their imagined color relative to the root, and parent edges show stored parity.
DSU parity: square is OK, diagonal breaks it
C++
1pair<int, int> find_set(int x) {
2 if (parent[x] == x) {
3 return {x, 0};
4 }
5
6 int old_parent = parent[x];
7 pair<int, int> res = find_set(old_parent);
8
9 parent[x] = res.first;
10 parity[x] ^= res.second;
11
12 return {parent[x], parity[x]};
13}
14
15bool union_sets(int x, int y) {
16 pair<int, int> A = find_set(x);
17 pair<int, int> B = find_set(y);
18
19 int X = A.first;
20 int px = A.second;
21
22 int Y = B.first;
23 int py = B.second;
24
25 if (X == Y) {
26 if (px == py) {
27 bipartite[X] = false;
28 }
29 return bipartite[X];
30 }
31
32 if (size[X] > size[Y]) {
33 swap(X, Y);
34 swap(px, py);
35 }
36
37 parent[X] = Y;
38 parity[X] = px ^ py ^ 1;
39 size[Y] += size[X];
40 bipartite[Y] = bipartite[Y] && bipartite[X];
41
42 return bipartite[Y];
43}
44
45int main() {
46 union_sets(1, 2);edge= (1, 2)X= 1Y= 2
47 union_sets(2, 3);
48 union_sets(3, 4);
49 union_sets(4, 1);
50 union_sets(1, 3);
51}
Edge 1: add (1, 2)
сатр 46
The first edge says that 1 and 2 must be different.
ҳамеша дуруст:For every new edge (x, y), x and y must have different parity.
Original graphграф
фаъолдар навбатдидашудаСкролл — зум · кашед — ҳаракат
DSU parity view: top row c=0, bottom row c=1самтдор
фаъолдар навбатдидашудаСкролл — зум · кашед — ҳаракат
стеки даъватҳо
union_sets(1, 2)
натиҷа
YES
edge(1, 2)X1Y2px0py0relationneed different, so parity[1] = 1resultYES
processed edges1statusbipartite
пахш кун
1 / 8
The main point is that the DSU does not need to recolor the whole graph. It only keeps enough information to answer this question:
“Are these two vertices already forced to be the same color or different colors?”
When the diagonal (1,3) appears, both endpoints already have parity 1 to the same root. So they are the same color, and the new edge contradicts bipartiteness.
Implementation
Complexity
Each operation without path compression:O(logn) using union by size.
Each operation with path compression: almost O(1) in practice.
Total time:O(qα(n)) with union by size and path compression.
Memory:O(n).
1. For every vertex v:
1. parent[v] = v
2. size[v] = 1
3. parity[v] = 0
4. bipartite[v] = true
2. find_set(x):
1. If parent[x] == x:
1. Return (x, 0)
2. Let old_parent = parent[x]
3. Find the root of old_parent and the parity from old_parent to the root
4. Compress x directly to the root
5. Update parity[x] so it becomes parity from x to the root
6. Return (parent[x], parity[x])
3. union_sets(x, y):
1. Find (X, px) for x
2. Find (Y, py) for y
3. If X == Y:
1. If px == py, then this edge connects equal colors
2. Mark bipartite[X] = false
3. Return whether this component is still bipartite
4. If size[X] > size[Y]:
1. Swap X and Y
2. Swap px and py
5. Attach X under Y
6. Set parity[X] = px xor py xor 1
7. Add size[X] to size[Y]
8. bipartite[Y] = bipartite[Y] and bipartite[X]
9. Return whether the merged component is still bipartite
4. Keep a global answer good = true.
5. After every added edge:
1. If union_sets(x, y) returns false, set good = false
2. Print YES if good is true, otherwise print NO
#include <bits/stdc++.h>using namespace std;struct DSU{ vector<int> parent; vector<int> size; vector<int> parity; vector<bool> bipartite; DSU(int n) : parent(n + 1, -1), size(n + 1, -1), parity(n + 1, 0), bipartite(n + 1, true){} void make_set(int x){ parent[x] = x; size[x] = 1; parity[x] = 0; bipartite[x] = true;} pair<int, int> find_set(int x){ if(parent[x] == x){ return{x, 0};} int old_parent = parent[x]; pair<int, int> res = find_set(old_parent); parent[x] = res.first; parity[x] ^= res.second; return{parent[x], parity[x]};} bool union_sets(int x, int y){ pair<int, int> A = find_set(x); pair<int, int> B = find_set(y); int X = A.first; int px = A.second; int Y = B.first; int py = B.second; if(X == Y){ if(px == py){ bipartite[X] = false;} return bipartite[X];} if(size[X]> size[Y]){ swap(X, Y); swap(px, py);} parent[X] = Y; parity[X] = px ^ py ^ 1; size[Y] += size[X]; bipartite[Y] = bipartite[Y] && bipartite[X]; return bipartite[Y];}};int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; DSU dsu(n); for(int i = 1; i <= n; i++){ dsu.make_set(i);} bool good = true; for(int i = 1; i <= q; i++){ int x, y; cin >> x >> y; if(!dsu.union_sets(x, y)){ good = false;} if(good){ cout << "YES\n";} else{ cout << "NO\n";}} return 0;}