上面写法是最原始的并查集算法，可能会导致查找的复杂度呈线性，当n非常大时，查找效率会变得很低。下面提供了两种优化的方法。

路径压缩是基于查找进行优化的，在查找的过程中将沿途查找过程中fa[x] != x的元素直接接到根节点上去。

int find(int x)
    if (fa[x] != x) {
        fa[x] = find(fa[x]);
    return fa[x];
按秩合并是基于合并进行优化的，给每个树都维护自己的秩（树的高度），使得每次合并时，都是秩小的树合并到秩大的树，使得整个树相对平衡，查找时的时间复杂度就接近nlgn。
 
int *fa = nullptr;
int *rank = nullptr;
void init(int n)
    fa = new int[n];
    rank = new int[n];
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
        rank[i] = 1; // 初始时秩为1
void merge(int i, int j)
    int x = find(i);
    int y = find(j);
    if (x == y) { //如果在同一棵树上，直接退出
        return;
    if (rank[x] < rank[y]) {
        fa[x] = y;
    } else {
        fa[y] = x;
        if (rank[x] == rank[y]) {
            rank[x]++;
上面路径压缩和按秩合并不要同时使用，因为在合并实现中有find操作，find操作会使得树的秩发生改变，但是并没有更新。解决办法后续补上~~
 
                    并查集主要解决一堆数据集合的合并和查询问题，是一种简单有效的数据结构。主要支持两种操作：合并：将两个不相交的元素合并。查询：查询两个元素是否在同一分组中。基本操作初始化合并查询优化算法...
并查集算法在很多算法中都会简单的涉及，比如最小生成树的kruskal算法等。其主要功能是检查不同元素是否属于同一个连通块。主要运用是在图相关的内容中。
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
在不同的不相交集合中选出一个代表元素，称为代表元
一般这个代表元代表这个集合。查找一...
				
最近在学可持久化数据结构，看了看可持久化并查集，无奈本人很菜，只会路径压缩实现并查集，不会其他方法，但是可持久化并查集用路径压缩会炸内存，所以我们需要用到按秩合并的方法去维护树形集合
按秩合并的特点，秩低的向秩高的进行合并
看下代码：
int findx(int x)
    if(x!=pre[x])
        pre[x]=findx(pre[x]);
1.并查集描述
一些有NNN个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
为了快速解决这些问题，便有了并查集的概念。
并查集维护了一个不相交的动态集的集合S1,S2,⋯ ,Sn{S_1,S_2,\cdots,S_n}S1​,S2​,⋯,Sn​，每个集合将有一个"首领"来标识该集...
				
文章目录一.简介：二.代表元法三.为什么需要并查集四.并查集的实现五.模板六.两种优化及其利弊
一.简介：
并查集是一种树形的数据结构，用于解决不相交（disjoint）集合的合并及查询问题，包含两种操作：
①合并两个集合
②查询某个元素属于哪个集合
二.代表元法
用一个集合中的某个元素来代表这个集合
比如集合{2，3，5，7，9}，不妨用7来代表这个集合，也可以理解为给这个集合编号/命名为7
并查集采用的正是这样的做法，因此它只解决不相交（不重叠）集合的问题，试想有两个集合都有元素7，并都用7来代表集合了
				
200.岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
示例 2：
输入：grid = [
				
题目：http://poj.org/problem?id=2492 
题的解答方法跟食物链差不多，可以看看食物链的解析再看这个。 
食物链  http://blog.csdn.net/dreambyday/article/details/65447189 
rela[x]=0表示同性 
rela[x]=1表示异性#include
#include
#includ
import java.util.HashMap;
class UnionFind {
    private HashMap<Integer, Integer> parent = new HashMap<>();    public UnionFind(int n) {
        for (int i = 0; i < n; i++) {
            parent.put(i, i);
    }    public int find(int x) {
        int parentX = parent.get(x);
        if (parentX == x) {
            return x;
        int ancestor = find(parentX);
        // 路径压缩
        parent.put(x, ancestor);
        return ancestor;
    }    public void union(int x, int y) {
        int ancestorX = find(x);
        int ancestorY = find(y);
        if (ancestorX == ancestorY) {
            return;
        parent.put(ancestorX, ancestorY);
}答案：我可以为您提供一段用Java写出并查集的代码： 
import java.util.HashMap;
class UnionFind {
    private HashMap<Integer, Integer> parent = new HashMap<>();    public UnionFind(int n) {
        for (int i = 0; i < n; i++) {
            parent.put(i, i);
    }    public int find(int x) {
        int parentX = parent.get(x);
        if (parentX == x) {
            return x;
        int ancestor = find(parentX);
        // 路径压缩
        parent.put(x, ancestor);
        return ancestor;
    }    public void union(int x, int y) {
        int ancestorX = find(x);
        int ancestorY = find(y);
        if (ancestorX == ancestorY) {
            return;
        parent.put(ancestorX, ancestorY);