> For the complete documentation index, see [llms.txt](https://blog.sunilgudivada.dev/notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blog.sunilgudivada.dev/notebook/data-structures-and-algorithms/topics/union-find-data-structure/dynamic-connectivity.md).

# Dynamic Connectivity

## Dynamic Connectivity

Given a set of N objects.

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

![](/files/QGA6M2pimNbgtYLDqAp4)

### Modelling the Connections

We assume "is connected to" is an equivalence relation:

* **Reflexive**: p is connected to p.
* **Symmetric**: if p is connected to q, then q is connected to p.
* **Transitive**: if p is connected to q and q is connected to r, then p is connected to

**Connected components:** Maximal set of objects that are mutually connected.

![](/files/H4tZP8NllgNoNX6Rq6We)

### **Implementing Operations**

**Find Query:** Check if two objects are in the same component.

**Union command**: Replace components containing two objects with their union.

![](/files/yWY9XaOW2e1Je6AZlT1r)

### Union Find Data Type - Java

```java
public class UF {

    // initialize union-find data structure with N objects (0 to N – 1)
    UF(int N);
    
    // add connection between p and q
    void union(int p, int q);
    
    // are p and q in the same component?
    boolean connected(int p, int q);
    
    // component identifier for p (0 to N – 1)
    int find(int p);
    
    // number of components
    int count();
}
```

##