> For the complete documentation index, see [llms.txt](https://syjohnson11.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://syjohnson11.gitbook.io/leetcode/12_union_find.md).

# 12. Union Find

## [并查集算法介绍](http://blog.csdn.net/dm_vincent/article/details/7655764)

* **元素的归属find O(1)**
* **集合的合并union O(1)**
* **在线算法，stream of input**
* **不支持delete**
*

### 为什么用HashMap不用int\[]?

* 虽然hashmap没有map array快
* 但如果输入的index差值太大的话，int\[]比hashmap浪费更多空间

## Number of Islands

* 经典的union find应用，因为要**频繁更新状态**
* 每次先add当前的index
* 然后逐步union邻居，在union函数里check邻居是否valid to union
* 注意unioin邻居之前先check boundary

```
public class Solution {
    private class UnionFind{
        private Map<Integer, Integer> father;//child->father, child is land, father is land
        private Map<Integer, Integer> size;//root-> count of island 
        private int cnt;
        public UnionFind(){
            father = new HashMap<>();
            size = new HashMap<>();
            cnt = 0;
        }
        private void add(Integer index){
            if(father.containsKey(index)){
                return;
            }
            father.put(index, index);
            size.put(index, 1);
            cnt++;
        }
        private Integer find(Integer index){
            if(!father.containsKey(index)) return null;
            Integer root = index;
            //find
            while(father.get(root) != root){
                root = father.get(root);
            }
            //compression
            while(index != root){
                father.put(index, root);
                Integer next = father.get(index);
                size.put(root, size.get(root) + 1);//update size
                index = next;
            }
            return root;
        }
        private void union(Integer p, Integer q){
            Integer pRoot = find(p);
            Integer qRoot = find(q);
            if(pRoot == null || qRoot == null) return;//either of them is water
            if(pRoot.equals(qRoot)) return;//already unioned

            int pSize = size.get(pRoot);
            int qSize = size.get(qRoot);
            if(pSize > qSize){
                father.put(qRoot, pRoot);//q->p
                size.put(pRoot, pSize + qSize);
            }else{
                father.put(pRoot, qRoot);
                size.put(qRoot, qSize + pSize);
                //size.put(pSize, 0);//no necessary
            }
            cnt--;
        }
        private int getCount(){
            return this.cnt;
        }
    }

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> res= new ArrayList<>();
        if(m <= 0 || n <= 0 || positions == null || positions.length < 1 || positions[0].length < 1) return res;
        UnionFind islands = new UnionFind();
        for(int[] position : positions){
            int x = position[0];
            int y = position[1];
            int index = x * n + y;

            islands.add(index);

            int[] dx = {0,0,1,-1};
            int[] dy = {1,-1,0,0};
            for(int i = 0; i < 4; i++){
                int xx = x + dx[i];
                int yy= y + dy[i];
                if(xx < 0 || xx >= m || yy < 0 || yy >= n) continue;//check boundary
                int neighbor = xx * n + yy;
                islands.union(index, neighbor);
            }
            res.add(islands.getCount());
        }
        return res;
    }
}
```

## Number of Connected Components

## Longest Consecutive Sequence

* weightedUnionFind模板
* 注意corner case, num == Integer.MIN\_VALUE, num == Integer.MAX\_VALUE
* 还有hashset的巧妙做法

```
class Solution {
    public class UnionFind {
        Map<Integer, Integer> childToParent;
        Map<Integer, Integer> rootToSize;
        int maxSize;
        public UnionFind() {
            childToParent = new HashMap<>();
            rootToSize = new HashMap<>();
            maxSize = 1;
        }

        private void add(Integer num) {
            if (childToParent.containsKey(num)) return;
            childToParent.put(num, num);
            rootToSize.put(num, 1);
        }

        private int getMaxSize() {
            return this.maxSize;
        }

        private Integer findRoot(Integer num) {
            if (!childToParent.containsKey(num)) return null;
            Integer root = num;
            while (childToParent.get(root) != root) {
                root = childToParent.get(root);
            }
            //path compression
            while (childToParent.get(num) != root) {
                Integer parent = childToParent.get(num);
                childToParent.put(num, root);
                num = parent;
            }
            return root;
        }

        private void union(Integer p, Integer q) {
            Integer pRoot = findRoot(p);
            Integer qRoot = findRoot(q);
            if (pRoot == null || qRoot == null || pRoot.equals(qRoot)) return;
            Integer pSize = rootToSize.get(pRoot);
            Integer qSize = rootToSize.get(qRoot);
            if (pSize < qSize) {
                childToParent.put(pRoot, qRoot);
                rootToSize.put(qRoot, pSize + qSize);
            } else {
                childToParent.put(qRoot, pRoot);
                rootToSize.put(pRoot, pSize + qSize);
            }
            maxSize = Math.max(maxSize, pSize + qSize);
        }
    }
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        UnionFind uf = new UnionFind();
        for (int num : nums) {
            uf.add(num);
            //corner case
            if (num != Integer.MIN_VALUE) {
                uf.union(num, num - 1);
            }
            if (num != Integer.MAX_VALUE) {
                uf.union(num, num + 1);
            }
        }
        return uf.getMaxSize();
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://syjohnson11.gitbook.io/leetcode/12_union_find.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.