# Disjoint Set Union

Authors: Benjamin Qi, Michael Cao, Andrew Wang

### Prerequisites

The Disjoint Set Union (DSU) data structure allows you to add edges to an initially empty graph and test whether two vertices of the graph are connected.

Focus Problem – read through this problem before continuing!

## Resources

Resources | |||
---|---|---|---|

CF | video explanation + problems for DSU | ||

CSA | both optimizations, diagrams | ||

PAPS | both optimizations, no diagrams | ||

CPH | small to large, diagrams | ||

IUSACO | path compression, diagrams | ||

TC | diagrams |

## Implementations

As the implementation is quite simple, you may prefer to use this in place of DFS for computing connected components.

C++

Check PAPS for the explanation. `e[x]`

contains the negation of the size of $x$'s component if $x$ is the representative of its component, and the parent of $x$ otherwise.

Resources | |||
---|---|---|---|

Benq (from KACTL) |

struct DSU {vi e; void init(int N) { e = vi(N,-1); }// get representive component, uses path compressionint get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }bool sameSet(int a, int b) { return get(a) == get(b); }int size(int x) { return -e[get(x)]; }bool unite(int x, int y) { // union by sizex = get(x), y = get(y); if (x == y) return 0;if (e[x] > e[y]) swap(x,y);e[x] += e[y]; e[y] = x; return 1;}};

Java

This implementation assumes that `disjoint`

is an array that starts such that `disjoint[i] = -1`

for every $0 <= i < n$.

public static int disjoint[]; //0 indexedpublic static int size[];//finds the "representative" node in a's componentpublic static int find(int v) {if (disjoint[v] == -1) {return v;}disjoint[v] = find(disjoint[v]);return disjoint[v];}

## Focus Problem Solution

Focus Problem – read through this problem before continuing!

The solution below is more verbose than some of the templates above. Use whichever implementation you are most comfortable with.

C++

#include <bits/stdc++.h>using namespace std;// sz[i] = size of component i, defaults to 1// pa[i] = parent of component i. If i is the root component, then pa[i] = i.int sz[200000], pa[200000];int get(int x) {return x == pa[x] ? x : pa[x] = get(pa[x]);

Java

import java.io.*;import java.util.*;public class Main {public static int disjoint[]; //0 indexedpublic static int size[];public static int find(int v) {if (disjoint[v] == -1) {return v;}

## Problems

### Standard

You should already be familiar with the DFS / Binary Search solutions to "Wormhole Sort" and "Moocast."

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

CSES | Easy | ## Show TagsDSU | ||||

Gold | Easy | ## Show TagsDSU | External Sol | |||

Gold | Easy | ## Show TagsDSU | ||||

Silver | Easy | ## Show TagsDSU | ||||

Gold | Easy | ## Show TagsDSU | ||||

CSA | Normal | ## Show TagsDSU | Check CSA |

### Harder

Don't worry about solving these if this is the first time you've encountered DSU.

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

Old Gold | Hard | ## Show TagsDSU | External Sol | |||

Baltic OI | Very Hard | ## Show TagsDSU | ||||

Gold | Very Hard | ## Show TagsDSU | External Sol | |||

Plat | Very Hard | ## Show TagsDSU |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!