// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
type DSU struct {
parent []int
rank []int
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
type DSU struct {
parent []int
rank []int
}
// NewDSU starts with n singletons — each node is its own representative.// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
type DSU struct {
parent []int
rank []int
}
// NewDSU starts with n singletons — each node is its own representative.
func NewDSU(n int) *DSU {
parent := make([]int, n)
rank := make([]int, n)
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
type DSU struct {
parent []int
rank []int
}
// NewDSU starts with n singletons — each node is its own representative.
func NewDSU(n int) *DSU {
parent := make([]int, n)
rank := make([]int, n)
for i := range parent {
parent[i] = i
}
return &DSU{parent, rank}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
type DSU struct {
parent []int
rank []int
}
// NewDSU starts with n singletons — each node is its own representative.
func NewDSU(n int) *DSU {
parent := make([]int, n)
rank := make([]int, n)
for i := range parent {
parent[i] = i
}
return &DSU{parent, rank}
}
// Find returns x's representative, and flattens the path so future calls are fast.// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
type DSU struct {
parent []int
rank []int
}
// NewDSU starts with n singletons — each node is its own representative.
func NewDSU(n int) *DSU {
parent := make([]int, n)
rank := make([]int, n)
for i := range parent {
parent[i] = i
}
return &DSU{parent, rank}
}
// Find returns x's representative, and flattens the path so future calls are fast.
func (d *DSU) Find(x int) int {
if d.parent[x] != x {
d.parent[x] = d.Find(d.parent[x]) // path compression
}
return d.parent[x]
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
type DSU struct {
parent []int
rank []int
}
// NewDSU starts with n singletons — each node is its own representative.
func NewDSU(n int) *DSU {
parent := make([]int, n)
rank := make([]int, n)
for i := range parent {
parent[i] = i
}
return &DSU{parent, rank}
}
// Find returns x's representative, and flattens the path so future calls are fast.
func (d *DSU) Find(x int) int {
if d.parent[x] != x {
d.parent[x] = d.Find(d.parent[x]) // path compression
}
return d.parent[x]
}
// Union merges the sets of x and y. Returns false if they were already joined.// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
type DSU struct {
parent []int
rank []int
}
// NewDSU starts with n singletons — each node is its own representative.
func NewDSU(n int) *DSU {
parent := make([]int, n)
rank := make([]int, n)
for i := range parent {
parent[i] = i
}
return &DSU{parent, rank}
}
// Find returns x's representative, and flattens the path so future calls are fast.
func (d *DSU) Find(x int) int {
if d.parent[x] != x {
d.parent[x] = d.Find(d.parent[x]) // path compression
}
return d.parent[x]
}
// Union merges the sets of x and y. Returns false if they were already joined.
func (d *DSU) Union(x, y int) bool {
rx, ry := d.Find(x), d.Find(y)
if rx == ry {
return false
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
type DSU struct {
parent []int
rank []int
}
// NewDSU starts with n singletons — each node is its own representative.
func NewDSU(n int) *DSU {
parent := make([]int, n)
rank := make([]int, n)
for i := range parent {
parent[i] = i
}
return &DSU{parent, rank}
}
// Find returns x's representative, and flattens the path so future calls are fast.
func (d *DSU) Find(x int) int {
if d.parent[x] != x {
d.parent[x] = d.Find(d.parent[x]) // path compression
}
return d.parent[x]
}
// Union merges the sets of x and y. Returns false if they were already joined.
func (d *DSU) Union(x, y int) bool {
rx, ry := d.Find(x), d.Find(y)
if rx == ry {
return false
}
// Union by rank: hang the shorter tree under the taller one to stay shallow.
// Heights only grow when two equal-rank trees merge.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
type DSU struct {
parent []int
rank []int
}
// NewDSU starts with n singletons — each node is its own representative.
func NewDSU(n int) *DSU {
parent := make([]int, n)
rank := make([]int, n)
for i := range parent {
parent[i] = i
}
return &DSU{parent, rank}
}
// Find returns x's representative, and flattens the path so future calls are fast.
func (d *DSU) Find(x int) int {
if d.parent[x] != x {
d.parent[x] = d.Find(d.parent[x]) // path compression
}
return d.parent[x]
}
// Union merges the sets of x and y. Returns false if they were already joined.
func (d *DSU) Union(x, y int) bool {
rx, ry := d.Find(x), d.Find(y)
if rx == ry {
return false
}
// Union by rank: hang the shorter tree under the taller one to stay shallow.
if d.rank[rx] < d.rank[ry] {
rx, ry = ry, rx
}
d.parent[ry] = rx
// Heights only grow when two equal-rank trees merge.
if d.rank[rx] == d.rank[ry] {
d.rank[rx]++
}
return true
}# parent points each node toward its set's representative; rank is an upper
# bound on a tree's height, used to keep unions shallow.
class DSU:
pass# parent points each node toward its set's representative; rank is an upper
# bound on a tree's height, used to keep unions shallow.
class DSU:
# __init__ starts with n singletons — each node is its own representative.# parent points each node toward its set's representative; rank is an upper
# bound on a tree's height, used to keep unions shallow.
class DSU:
# __init__ starts with n singletons — each node is its own representative.
def __init__(self, n):
self.parent = [0] * n
self.rank = [0] * n# parent points each node toward its set's representative; rank is an upper
# bound on a tree's height, used to keep unions shallow.
class DSU:
# __init__ starts with n singletons — each node is its own representative.
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n# parent points each node toward its set's representative; rank is an upper
# bound on a tree's height, used to keep unions shallow.
class DSU:
# __init__ starts with n singletons — each node is its own representative.
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
# find returns x's representative, and flattens the path so future calls are fast.# parent points each node toward its set's representative; rank is an upper
# bound on a tree's height, used to keep unions shallow.
class DSU:
# __init__ starts with n singletons — each node is its own representative.
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
# find returns x's representative, and flattens the path so future calls are fast.
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]# parent points each node toward its set's representative; rank is an upper
# bound on a tree's height, used to keep unions shallow.
class DSU:
# __init__ starts with n singletons — each node is its own representative.
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
# find returns x's representative, and flattens the path so future calls are fast.
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
# union merges the sets of x and y. Returns False if they were already joined.# parent points each node toward its set's representative; rank is an upper
# bound on a tree's height, used to keep unions shallow.
class DSU:
# __init__ starts with n singletons — each node is its own representative.
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
# find returns x's representative, and flattens the path so future calls are fast.
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
# union merges the sets of x and y. Returns False if they were already joined.
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False# parent points each node toward its set's representative; rank is an upper
# bound on a tree's height, used to keep unions shallow.
class DSU:
# __init__ starts with n singletons — each node is its own representative.
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
# find returns x's representative, and flattens the path so future calls are fast.
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
# union merges the sets of x and y. Returns False if they were already joined.
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False
# Union by rank: hang the shorter tree under the taller one to stay shallow.
# Heights only grow when two equal-rank trees merge.# parent points each node toward its set's representative; rank is an upper
# bound on a tree's height, used to keep unions shallow.
class DSU:
# __init__ starts with n singletons — each node is its own representative.
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
# find returns x's representative, and flattens the path so future calls are fast.
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
# union merges the sets of x and y. Returns False if they were already joined.
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False
# Union by rank: hang the shorter tree under the taller one to stay shallow.
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
# Heights only grow when two equal-rank trees merge.
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return True// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// The constructor starts with n singletons — each node is its own representative.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// The constructor starts with n singletons — each node is its own representative.
constructor(n) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// The constructor starts with n singletons — each node is its own representative.
constructor(n) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// The constructor starts with n singletons — each node is its own representative.
constructor(n) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
// find returns x's representative, and flattens the path so future calls are fast.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// The constructor starts with n singletons — each node is its own representative.
constructor(n) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
// find returns x's representative, and flattens the path so future calls are fast.
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// The constructor starts with n singletons — each node is its own representative.
constructor(n) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
// find returns x's representative, and flattens the path so future calls are fast.
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
// union merges the sets of x and y. Returns false if they were already joined.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// The constructor starts with n singletons — each node is its own representative.
constructor(n) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
// find returns x's representative, and flattens the path so future calls are fast.
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
// union merges the sets of x and y. Returns false if they were already joined.
union(x, y) {
let rx = this.find(x), ry = this.find(y);
if (rx === ry) return false;
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// The constructor starts with n singletons — each node is its own representative.
constructor(n) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
// find returns x's representative, and flattens the path so future calls are fast.
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
// union merges the sets of x and y. Returns false if they were already joined.
union(x, y) {
let rx = this.find(x), ry = this.find(y);
if (rx === ry) return false;
// Union by rank: hang the shorter tree under the taller one to stay shallow.
// Heights only grow when two equal-rank trees merge.
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// The constructor starts with n singletons — each node is its own representative.
constructor(n) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
// find returns x's representative, and flattens the path so future calls are fast.
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
// union merges the sets of x and y. Returns false if they were already joined.
union(x, y) {
let rx = this.find(x), ry = this.find(y);
if (rx === ry) return false;
// Union by rank: hang the shorter tree under the taller one to stay shallow.
if (this.rank[rx] < this.rank[ry]) [rx, ry] = [ry, rx];
this.parent[ry] = rx;
// Heights only grow when two equal-rank trees merge.
if (this.rank[rx] === this.rank[ry]) this.rank[rx]++;
return true;
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private parent: number[];
private rank: number[];
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private parent: number[];
private rank: number[];
// The constructor starts with n singletons — each node is its own representative.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private parent: number[];
private rank: number[];
// The constructor starts with n singletons — each node is its own representative.
constructor(n: number) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private parent: number[];
private rank: number[];
// The constructor starts with n singletons — each node is its own representative.
constructor(n: number) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private parent: number[];
private rank: number[];
// The constructor starts with n singletons — each node is its own representative.
constructor(n: number) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
// find returns x's representative, and flattens the path so future calls are fast.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private parent: number[];
private rank: number[];
// The constructor starts with n singletons — each node is its own representative.
constructor(n: number) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
// find returns x's representative, and flattens the path so future calls are fast.
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private parent: number[];
private rank: number[];
// The constructor starts with n singletons — each node is its own representative.
constructor(n: number) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
// find returns x's representative, and flattens the path so future calls are fast.
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
// union merges the sets of x and y. Returns false if they were already joined.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private parent: number[];
private rank: number[];
// The constructor starts with n singletons — each node is its own representative.
constructor(n: number) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
// find returns x's representative, and flattens the path so future calls are fast.
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
// union merges the sets of x and y. Returns false if they were already joined.
union(x: number, y: number): boolean {
let rx = this.find(x), ry = this.find(y);
if (rx === ry) return false;
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private parent: number[];
private rank: number[];
// The constructor starts with n singletons — each node is its own representative.
constructor(n: number) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
// find returns x's representative, and flattens the path so future calls are fast.
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
// union merges the sets of x and y. Returns false if they were already joined.
union(x: number, y: number): boolean {
let rx = this.find(x), ry = this.find(y);
if (rx === ry) return false;
// Union by rank: hang the shorter tree under the taller one to stay shallow.
// Heights only grow when two equal-rank trees merge.
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private parent: number[];
private rank: number[];
// The constructor starts with n singletons — each node is its own representative.
constructor(n: number) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0);
for (let i = 0; i < n; i++) this.parent[i] = i;
}
// find returns x's representative, and flattens the path so future calls are fast.
find(x: number): number {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // path compression
}
return this.parent[x];
}
// union merges the sets of x and y. Returns false if they were already joined.
union(x: number, y: number): boolean {
let rx = this.find(x), ry = this.find(y);
if (rx === ry) return false;
// Union by rank: hang the shorter tree under the taller one to stay shallow.
if (this.rank[rx] < this.rank[ry]) [rx, ry] = [ry, rx];
this.parent[ry] = rx;
// Heights only grow when two equal-rank trees merge.
if (this.rank[rx] === this.rank[ry]) this.rank[rx]++;
return true;
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private final int[] parent;
private final int[] rank;
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private final int[] parent;
private final int[] rank;
// The constructor starts with n singletons — each node is its own representative.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private final int[] parent;
private final int[] rank;
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) {
parent = new int[n];
rank = new int[n];
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private final int[] parent;
private final int[] rank;
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private final int[] parent;
private final int[] rank;
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns x's representative, and flattens the path so future calls are fast.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private final int[] parent;
private final int[] rank;
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns x's representative, and flattens the path so future calls are fast.
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private final int[] parent;
private final int[] rank;
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns x's representative, and flattens the path so future calls are fast.
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
// union merges the sets of x and y. Returns false if they were already joined.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private final int[] parent;
private final int[] rank;
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns x's representative, and flattens the path so future calls are fast.
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
// union merges the sets of x and y. Returns false if they were already joined.
boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) {
return false;
}
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private final int[] parent;
private final int[] rank;
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns x's representative, and flattens the path so future calls are fast.
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
// union merges the sets of x and y. Returns false if they were already joined.
boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) {
return false;
}
// Union by rank: hang the shorter tree under the taller one to stay shallow.
// Heights only grow when two equal-rank trees merge.
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
private final int[] parent;
private final int[] rank;
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns x's representative, and flattens the path so future calls are fast.
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
// union merges the sets of x and y. Returns false if they were already joined.
boolean union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) {
return false;
}
// Union by rank: hang the shorter tree under the taller one to stay shallow.
if (rank[rx] < rank[ry]) {
int swap = rx; rx = ry; ry = swap;
}
parent[ry] = rx;
// Heights only grow when two equal-rank trees merge.
if (rank[rx] == rank[ry]) {
rank[rx]++;
}
return true;
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
public class DSU {
private readonly int[] parent;
private readonly int[] rank;
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
public class DSU {
private readonly int[] parent;
private readonly int[] rank;
// The constructor starts with n singletons — each node is its own representative.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
public class DSU {
private readonly int[] parent;
private readonly int[] rank;
// The constructor starts with n singletons — each node is its own representative.
public DSU(int n) {
parent = new int[n];
rank = new int[n];
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
public class DSU {
private readonly int[] parent;
private readonly int[] rank;
// The constructor starts with n singletons — each node is its own representative.
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
public class DSU {
private readonly int[] parent;
private readonly int[] rank;
// The constructor starts with n singletons — each node is its own representative.
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// Find returns x's representative, and flattens the path so future calls are fast.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
public class DSU {
private readonly int[] parent;
private readonly int[] rank;
// The constructor starts with n singletons — each node is its own representative.
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// Find returns x's representative, and flattens the path so future calls are fast.
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]); // path compression
}
return parent[x];
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
public class DSU {
private readonly int[] parent;
private readonly int[] rank;
// The constructor starts with n singletons — each node is its own representative.
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// Find returns x's representative, and flattens the path so future calls are fast.
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]); // path compression
}
return parent[x];
}
// Union merges the sets of x and y. Returns false if they were already joined.
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
public class DSU {
private readonly int[] parent;
private readonly int[] rank;
// The constructor starts with n singletons — each node is its own representative.
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// Find returns x's representative, and flattens the path so future calls are fast.
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]); // path compression
}
return parent[x];
}
// Union merges the sets of x and y. Returns false if they were already joined.
public bool Union(int x, int y) {
int rx = Find(x), ry = Find(y);
if (rx == ry) {
return false;
}
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
public class DSU {
private readonly int[] parent;
private readonly int[] rank;
// The constructor starts with n singletons — each node is its own representative.
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// Find returns x's representative, and flattens the path so future calls are fast.
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]); // path compression
}
return parent[x];
}
// Union merges the sets of x and y. Returns false if they were already joined.
public bool Union(int x, int y) {
int rx = Find(x), ry = Find(y);
if (rx == ry) {
return false;
}
// Union by rank: hang the shorter tree under the taller one to stay shallow.
// Heights only grow when two equal-rank trees merge.
}
}// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
public class DSU {
private readonly int[] parent;
private readonly int[] rank;
// The constructor starts with n singletons — each node is its own representative.
public DSU(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// Find returns x's representative, and flattens the path so future calls are fast.
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]); // path compression
}
return parent[x];
}
// Union merges the sets of x and y. Returns false if they were already joined.
public bool Union(int x, int y) {
int rx = Find(x), ry = Find(y);
if (rx == ry) {
return false;
}
// Union by rank: hang the shorter tree under the taller one to stay shallow.
if (rank[rx] < rank[ry]) {
int swap = rx; rx = ry; ry = swap;
}
parent[ry] = rx;
// Heights only grow when two equal-rank trees merge.
if (rank[rx] == rank[ry]) {
rank[rx]++;
}
return true;
}
}#include <stdbool.h>
#include <stdlib.h>
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
typedef struct {
int* parent;
int* rank;
} DSU;#include <stdbool.h>
#include <stdlib.h>
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
typedef struct {
int* parent;
int* rank;
} DSU;
// dsuNew starts with n singletons — each node is its own representative.
#include <stdbool.h>
#include <stdlib.h>
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
typedef struct {
int* parent;
int* rank;
} DSU;
// dsuNew starts with n singletons — each node is its own representative.
DSU* dsuNew(int n) {
DSU* d = malloc(sizeof(DSU));
d->parent = malloc(n * sizeof(int));
d->rank = calloc(n, sizeof(int));
}#include <stdbool.h>
#include <stdlib.h>
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
typedef struct {
int* parent;
int* rank;
} DSU;
// dsuNew starts with n singletons — each node is its own representative.
DSU* dsuNew(int n) {
DSU* d = malloc(sizeof(DSU));
d->parent = malloc(n * sizeof(int));
d->rank = calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
d->parent[i] = i;
}
return d;
}#include <stdbool.h>
#include <stdlib.h>
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
typedef struct {
int* parent;
int* rank;
} DSU;
// dsuNew starts with n singletons — each node is its own representative.
DSU* dsuNew(int n) {
DSU* d = malloc(sizeof(DSU));
d->parent = malloc(n * sizeof(int));
d->rank = calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
d->parent[i] = i;
}
return d;
}
// dsuFind returns x's representative, and flattens the path so future calls are fast.
#include <stdbool.h>
#include <stdlib.h>
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
typedef struct {
int* parent;
int* rank;
} DSU;
// dsuNew starts with n singletons — each node is its own representative.
DSU* dsuNew(int n) {
DSU* d = malloc(sizeof(DSU));
d->parent = malloc(n * sizeof(int));
d->rank = calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
d->parent[i] = i;
}
return d;
}
// dsuFind returns x's representative, and flattens the path so future calls are fast.
int dsuFind(DSU* d, int x) {
if (d->parent[x] != x) {
d->parent[x] = dsuFind(d, d->parent[x]); // path compression
}
return d->parent[x];
}#include <stdbool.h>
#include <stdlib.h>
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
typedef struct {
int* parent;
int* rank;
} DSU;
// dsuNew starts with n singletons — each node is its own representative.
DSU* dsuNew(int n) {
DSU* d = malloc(sizeof(DSU));
d->parent = malloc(n * sizeof(int));
d->rank = calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
d->parent[i] = i;
}
return d;
}
// dsuFind returns x's representative, and flattens the path so future calls are fast.
int dsuFind(DSU* d, int x) {
if (d->parent[x] != x) {
d->parent[x] = dsuFind(d, d->parent[x]); // path compression
}
return d->parent[x];
}
// dsuUnion merges the sets of x and y. Returns false if they were already joined.
#include <stdbool.h>
#include <stdlib.h>
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
typedef struct {
int* parent;
int* rank;
} DSU;
// dsuNew starts with n singletons — each node is its own representative.
DSU* dsuNew(int n) {
DSU* d = malloc(sizeof(DSU));
d->parent = malloc(n * sizeof(int));
d->rank = calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
d->parent[i] = i;
}
return d;
}
// dsuFind returns x's representative, and flattens the path so future calls are fast.
int dsuFind(DSU* d, int x) {
if (d->parent[x] != x) {
d->parent[x] = dsuFind(d, d->parent[x]); // path compression
}
return d->parent[x];
}
// dsuUnion merges the sets of x and y. Returns false if they were already joined.
bool dsuUnion(DSU* d, int x, int y) {
int rx = dsuFind(d, x), ry = dsuFind(d, y);
if (rx == ry) {
return false;
}
}#include <stdbool.h>
#include <stdlib.h>
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
typedef struct {
int* parent;
int* rank;
} DSU;
// dsuNew starts with n singletons — each node is its own representative.
DSU* dsuNew(int n) {
DSU* d = malloc(sizeof(DSU));
d->parent = malloc(n * sizeof(int));
d->rank = calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
d->parent[i] = i;
}
return d;
}
// dsuFind returns x's representative, and flattens the path so future calls are fast.
int dsuFind(DSU* d, int x) {
if (d->parent[x] != x) {
d->parent[x] = dsuFind(d, d->parent[x]); // path compression
}
return d->parent[x];
}
// dsuUnion merges the sets of x and y. Returns false if they were already joined.
bool dsuUnion(DSU* d, int x, int y) {
int rx = dsuFind(d, x), ry = dsuFind(d, y);
if (rx == ry) {
return false;
}
// Union by rank: hang the shorter tree under the taller one to stay shallow.
// Heights only grow when two equal-rank trees merge.
}#include <stdbool.h>
#include <stdlib.h>
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
typedef struct {
int* parent;
int* rank;
} DSU;
// dsuNew starts with n singletons — each node is its own representative.
DSU* dsuNew(int n) {
DSU* d = malloc(sizeof(DSU));
d->parent = malloc(n * sizeof(int));
d->rank = calloc(n, sizeof(int));
for (int i = 0; i < n; i++) {
d->parent[i] = i;
}
return d;
}
// dsuFind returns x's representative, and flattens the path so future calls are fast.
int dsuFind(DSU* d, int x) {
if (d->parent[x] != x) {
d->parent[x] = dsuFind(d, d->parent[x]); // path compression
}
return d->parent[x];
}
// dsuUnion merges the sets of x and y. Returns false if they were already joined.
bool dsuUnion(DSU* d, int x, int y) {
int rx = dsuFind(d, x), ry = dsuFind(d, y);
if (rx == ry) {
return false;
}
// Union by rank: hang the shorter tree under the taller one to stay shallow.
if (d->rank[rx] < d->rank[ry]) {
int swap = rx; rx = ry; ry = swap;
}
d->parent[ry] = rx;
// Heights only grow when two equal-rank trees merge.
if (d->rank[rx] == d->rank[ry]) {
d->rank[rx]++;
}
return true;
}#include <vector>
using namespace std;
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// Named rnk, not rank: <type_traits> already defines std::rank, which
// "using namespace std" would drag into scope.
vector<int> parent, rnk;
public:
};#include <vector>
using namespace std;
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// Named rnk, not rank: <type_traits> already defines std::rank, which
// "using namespace std" would drag into scope.
vector<int> parent, rnk;
public:
// The constructor starts with n singletons — each node is its own representative.
};#include <vector>
using namespace std;
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// Named rnk, not rank: <type_traits> already defines std::rank, which
// "using namespace std" would drag into scope.
vector<int> parent, rnk;
public:
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) : parent(n), rnk(n, 0) {
}
};#include <vector>
using namespace std;
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// Named rnk, not rank: <type_traits> already defines std::rank, which
// "using namespace std" would drag into scope.
vector<int> parent, rnk;
public:
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) : parent(n), rnk(n, 0) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
};#include <vector>
using namespace std;
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// Named rnk, not rank: <type_traits> already defines std::rank, which
// "using namespace std" would drag into scope.
vector<int> parent, rnk;
public:
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) : parent(n), rnk(n, 0) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns x's representative, and flattens the path so future calls are fast.
};#include <vector>
using namespace std;
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// Named rnk, not rank: <type_traits> already defines std::rank, which
// "using namespace std" would drag into scope.
vector<int> parent, rnk;
public:
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) : parent(n), rnk(n, 0) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns x's representative, and flattens the path so future calls are fast.
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
};#include <vector>
using namespace std;
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// Named rnk, not rank: <type_traits> already defines std::rank, which
// "using namespace std" would drag into scope.
vector<int> parent, rnk;
public:
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) : parent(n), rnk(n, 0) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns x's representative, and flattens the path so future calls are fast.
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
// unite merges the sets of x and y. Returns false if they were already joined.
};#include <vector>
using namespace std;
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// Named rnk, not rank: <type_traits> already defines std::rank, which
// "using namespace std" would drag into scope.
vector<int> parent, rnk;
public:
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) : parent(n), rnk(n, 0) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns x's representative, and flattens the path so future calls are fast.
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
// unite merges the sets of x and y. Returns false if they were already joined.
bool unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) {
return false;
}
}
};#include <vector>
using namespace std;
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// Named rnk, not rank: <type_traits> already defines std::rank, which
// "using namespace std" would drag into scope.
vector<int> parent, rnk;
public:
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) : parent(n), rnk(n, 0) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns x's representative, and flattens the path so future calls are fast.
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
// unite merges the sets of x and y. Returns false if they were already joined.
bool unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) {
return false;
}
// Union by rank: hang the shorter tree under the taller one to stay shallow.
// Heights only grow when two equal-rank trees merge.
}
};#include <vector>
using namespace std;
// parent points each node toward its set's representative; rank is an upper
// bound on a tree's height, used to keep unions shallow.
class DSU {
// Named rnk, not rank: <type_traits> already defines std::rank, which
// "using namespace std" would drag into scope.
vector<int> parent, rnk;
public:
// The constructor starts with n singletons — each node is its own representative.
DSU(int n) : parent(n), rnk(n, 0) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// find returns x's representative, and flattens the path so future calls are fast.
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
// unite merges the sets of x and y. Returns false if they were already joined.
bool unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) {
return false;
}
// Union by rank: hang the shorter tree under the taller one to stay shallow.
if (rnk[rx] < rnk[ry]) {
swap(rx, ry);
}
parent[ry] = rx;
// Heights only grow when two equal-rank trees merge.
if (rnk[rx] == rnk[ry]) {
rnk[rx]++;
}
return true;
}
};Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.