并查集模板-JZTXT

static int[] fa;

	public static void main(String[] args) {
		
	}

	/**
	 * 初始化
	 */
	static void init() {
		for (int i = 1; i < fa.length; i++) {
			fa[i] = i;
		}
	}

	/**
	 * 查询
	 */
	static int find(int i) {
		if (fa[i] == i) {// 递归出口，当到达了祖先位置，就返回祖先
			return i;
		} else {
			return find(fa[i]);// 不断向上查找祖先
		}
	}

	/**
	 * 路径压缩              必须有，否则爆时间
	 */
	static int find2(int i) {
		if (fa[i] == i) {// 递归出口，当到达了祖先位置，就返回祖先
			return i;
		} else {
			fa[i] = find(fa[i]); // 该步进行了路径压缩
			return fa[i];// 返回父节点
		}
	}

	/**
	 * 合并
	 */
	static void union(int i, int j) {
		int ifa = find(i);// 找到 i 的祖先
		int jfa = find(j);// 找到 j 的祖先
		fa[ifa] = jfa;// i 的祖先指向 j 的祖先
	}