# Quick Find - Eager Approach

## Quick Find - Eager Approach

**Data structure :** Integer Array `id[]`of length N

**Interpretation:**

**Find:** `p` and `q` are connected iff they have the same id.

**Union:** To merge components containing `p` and `q`, change all entries whose id equals `id[p]` to `id[q]`

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

After `union(6,1)`

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

### Java Implementation

{% code title="QuickFindUF.java" %}

```java
public class QuickFindUF
{
   private int[] id;
   
   // set id of each object to itself (N array accesses)
   public QuickFindUF(int N)
   {
      id = new int[N];
      for (int i = 0; i < N; i++)
         id[i] = i;
   }
   
   // check whether p and q are in the same component (2 array accesses)
   public boolean connected(int p, int q)
   {  
      return id[p] == id[q];  
   }
   
   // change all entries with id[p] to id[q] (at most 2N + 2 array accesses)
   public void union(int p, int q)
   {
      int pid = id[p];
      int qid = id[q];
      for (int i = 0; i < id.length; i++)
         if (id[i] == pid) id[i] = qid;
   }
}
```

{% endcode %}