import java.util.*; import java.lang.*; import java.io.*; // The main method must be in a class named "Main". class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] ps = new int[n]; for (int i=0; i rank[yRoot]) { parent[yRoot] = xRoot; // yの親をxに更新 size[xRoot] = xSize + ySize; // 木を構成する要素の数を更新 treeCount--; } else if (rank[xRoot] < rank[yRoot]) { parent[xRoot] = yRoot; size[yRoot] = ySize + xSize; treeCount--; } else if (xRoot != yRoot) { parent[yRoot] = xRoot; rank[xRoot]++; // 同じ高さの木がルートの子として着くから大きさ++; size[xRoot] = xSize + ySize; treeCount--; } } /** * 要素の根を返す。 経路圧縮も同時に行う。(1→3→2となっていて2をfindした際、1→3,2と木の深さを浅くする。) * * @param i * @return 要素iの根 (1→3→2となっていて2をfindした際、1となる。) */ public int find(int i) { if (i != parent[i]) { parent[i] = find(parent[i]); } return parent[i]; } /** * 2つの要素が同じ木に属するかどうかを返す。 * * @param x : 1つ目の要素 * @param y : 2つ目の要素 * @return 同じ木に属していればtrue */ public boolean same(int x, int y) { return find(x) == find(y); } /** * 木の高さを返す。 * * @param i : 高さを調べたい木の根の番号 * @return 木の高さ */ public int getRank(int i) { return rank[i]; } /** * 木を構成する要素の数を返す。 * * @param i : 要素数を調べたい木の根の番号 * @return 木を構成する要素の数 */ public int getSize(int i) { return size[find(i)]; } /** * 木の数を返す。 * * @return 木の数。 */ public int getTreeCount() { return treeCount; } }