主要是并查集的优化
union 基于 rank 的优化
import java.util.*; import java.io.*; public class Main { static public int[] p;//根节点 static public int[] rank;//秩 public static void init(int n){ //初始化 p = new int[n+1]; for(int i=0;i<p.length;i++){ p[i] = i; } rank = new int[n+1]; for(int i=0;i<rank.length;i++){ rank[i] = 0; } } public static int find(int x){ return x==p[x] ? x:(p[x] = find(p[x])); } public static void union(int x1, int x2){ // 查找根节点 int f1 = find(x1); int f2 = find(x2); if(f1 == f2){ return; } /** * 按秩合并两个集合,rank大的作为父节点,以减少树的层数 * 秩较小的作为子树,放到秩较大的节点下面 */ if(rank[f1] > rank[f2]){ p[f2] = f1; }else{ p[f1] = f2; if(rank[f1] == rank[f2]){//新树秩+1 ++rank[f2]; } } } public static boolean isSameSet(int a, int b){ return find(a)== find(b); } public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String line = bf.readLine(); String[] strings = line.split(" "); int N = Integer.parseInt(strings[0]); int M = Integer.parseInt(strings[1]); init(N); ArrayList res = new ArrayList(); for(int i=0;i<M;i++){ String[] ss = bf.readLine().split(" "); int opt = Integer.parseInt(ss[0]); int a = Integer.parseInt(ss[1]); int b = Integer.parseInt(ss[2]); if(opt == 1){ res.add(isSameSet(a,b)==true?"Yes":"No"); }else{ union(a,b); } } //输出结果 StringBuilder sb = new StringBuilder(); if(res.size() >= 1){ sb.append(res.get(0)); } for(int i=1;i<res.size();i++){ sb.append("\n" + res.get(i)); } System.out.println(sb.toString()); } } /* 4 5 1 1 2 2 2 3 2 1 3 1 1 1 1 2 3 No Yes Yes */