> 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?

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-8a9613241ea8d2f9db941bc929db3495a1cf6ca9%2Fimage%20\(9\).png?alt=media)

### 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.

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-a102cd5de7ab6baef8ac67cd47f1aee35e735f1c%2Fimage%20\(16\).png?alt=media)

### **Implementing Operations**

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

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

![](https://1133441777-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MP3gpNOfmHBf90k26iY%2Fuploads%2Fgit-blob-eb6b3ddb911e6c05b2cd1cd08c267c0d58523f7c%2Fimage%20\(13\).png?alt=media)

### 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();
}
```

##