# Union Find

Typically, Union-find use `Tree`

data structure and provide two methods,

`Union`

: combine two sets into one`Find`

: Determine which data set that an element belongs to.

## Abstractions

1 | Objects |

1 | Disjoint sets of objects |

1 | Find query: are objects 2 and 9 in the same set? |

1 | Union command: merge sets containing 3 and 8. |

## Example in life: Friend Circle

Imaging that we have n students in school. At the beginning, they don’t know each other.

When the time goes by, circle of friends start to form and grow. If a and b are friends, b and c are friend, then we say that a and c becomes indirect friends, and a, b, c are in the same friend circle.

We can use `Union`

function to establish connections between two students, and use `find`

function to determine if `student i`

and `student j`

are in the same friend circle.

## Basic Idea

we can use `Tree`

data structure to store the root (group ID) information of a

node. In the above example, each student is in a group of themselves at the beginning.

1 | id[i] is parent of i |

we define an array `group[]`

, each value denote as group ID. (Obviously, at the beginning, group ID are index of themselves)

1 | int[] group = new int[n]; |

## Union

`Union(x,y)`

The idea of union is that, we unite their root. (which means that, we find roots of `x`

and `y`

respectively, and let one root point to another root)

1 | Union(2,9); |

1 | public void unite(int e, int g) { |

## Find

`Find(x,y)`

the function is quite simple, just check if they have the same root (ID).

1 | public boolean find(int p, int q) { |

### Find Root

How do we know that the value is the Group ID?

When `root(i) == i`

, we are sure that id(i) is the root and i is the group ID.

1 | public int root(int i) { |

## Problem

We’ve known that we use `tree`

to store the parent information so that we can traverse and find the root.

but if the tree is very deep, it may take long time to operate `root`

function.

The worst case for finding root (group ID) is **O(N)**

1 | i 0 1 2 3 4 5 6 7 8 9 |

## Improvement

To avoid this problem, one possible solution is `Path Compression`

Just after computing the root of i, set the id of each examined node to root(i).

1 | public int root(int i) { |

## Sample Question: Friend Circle

There are `N`

students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a `N*N`

matrix `M`

representing the friend relationship between students in the class. If `M[i][j] = 1`

, then the `ith`

and `jth`

students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Example 1:

1 | Input: |

Output: 2

**Explanation**:The 0th and 1st students are direct friends, so they are in a friend circle.

The 2nd student himself is in a friend circle. So return 2.

Example 2:

1 | Input: |

Output: 1

**Explanation**:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,

so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

1 | public class Solution { |

Reference Algorithm-Union-Find