import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int s = sc.nextInt()-1; int g = sc.nextInt()-1; List edges = new ArrayList<>(); for (int i=0; i canConnectEdges = new ArrayList<>(); for (Edge edge : edges) { boolean connect = true; for (int j=0; j 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; } } //グラフのエッジ(辺)を格納するクラス class Edge { public final int from, to; /**コンストラクタ * @param : from 頂点 * @param : to つながっている頂点 */ Edge(int from, int to) { this.from = from; this.to = to; } } //無向グラフクラス class Graph { //隣接リストを表すリストのリスト(ある頂点が、どの頂点とつながっているかを保持するリスト) List> list = null; /**コンストラクタ * @param edges : 辺 * @param n : 頂点の個数 * */ Graph(List edges, int n) { list = new ArrayList<>(); for (int i = 0; i < n; i++) { list.add(new ArrayList<>()); } //無向グラフにエッジを追加します for (Edge edge: edges) { int from = edge.from; int to = edge.to; list.get(from).add(edge); list.get(to).add(edge); } } public int size() { return list.size(); } public List getEdgsList(int vNum) { return list.get(vNum); } }