### Introduction

Today we often face a certain kind of problem called dynamic connectivity:

Given a set of N objects.

- Union command: connect two objects.
- Find/connected query: is there a path connecting the two objects?

So there are 2 types of operation in this:

- Find query. Check if two objects are in the same component.
- Union command. Replace components containing two objects with their union.

### Problem Statement

First read in an integer N, each object is less than N (for each element, the minimum value is 0, the maximum value is N-1).

Second, read in an integer T (the number of pairs that need to be unioned), followed by T lines of pairs.

Last, read in an integer TNUM (the number of find queries), followed by TNUM lines of pairs.

If they are not yet connected, connect them. Then we will execute find() queries on the data, if they are connected, output YES, otherwise output NO.

Here is the sample input:

1 | 10 11 |

Here is the sample output:

1 | NO |

### Quick-Find

This is a naive algorithm that we could thought of. We have an integer array id[] of length N. If 2 elements p and q are connected, they should have the same id. That is to say, id[p] == id[q]. So the find operation is to check if p and q have the same id. And the union operation is to merge components containing p and q, change all entries whose id equals id[p] to id[q].

Here is my implementation in C++ code:

**quick-find.cpp**

1 | #include <iostream> |

The defect of this algorithm is that it is too slow, if there are N union commands on N objects, then the time cost of union operation is O(n×n).

### Quick-Union

Here is a better algorithm, we still have an integer array id[] of length N, and id[i] is the parent of i.

- Find. Check if p and q have the same root.
- Union. To merge components containing p and q,

set the id of p’s root to the id of q’s root.

Here is my implementation in C++ code:

**quick-union.cpp**

1 | #include <iostream> |

But this algorithm has 2 defects:

- Trees can get tall.
- Find too expensive (could be N array accesses).

### Weighted Quick-Union

Here is an improved quick-union algorithm called *Weighted Quick-Union*.

Rather than arbitrarily connecting the second tree to the first for union() in the quick-union algorithm, we keep track of the size of each tree and always connect the smaller tree to the larger one.

￼

I have implemented this algorithm in both C++ and Java. See below.

Here is my implementation in Java code:

**WeightedQuickUnion.java**

1 | import java.util.Scanner; |

Here is my implementation in C++ code:

**weighted-quick-union.cpp**

1 | #include <iostream> |

Now the time cost of find() is O(logn), the time cost of union operation is also O(logn), which is much faster than the former O(n) version algorithm.