（并查集）洛谷P3367，并查集的模板

一个模板 先将所有的节点都初始化为自己也就是自己是自己的老大之后Find就是顺腾摸瓜到最高级别的需要注意的是要是普通的return Find(boss[x])的话需要逐渐的去返回最大的值要是用boss[x]就会将最大以外的所有的子节点都变成同一个水平这样的话查找的速度就变的更加快速了import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import static java.lang.System.*; public class Main { static int[] boss; public static void main(String[] args) throws IOException { BufferedReader brnew BufferedReader(new InputStreamReader(in)); StreamTokenizer stnew StreamTokenizer(br); st.nextToken(); int N(int)st.nval; st.nextToken(); int M(int)st.nval; bossnew int[N1]; DSU(boss); for (int i 0; i M; i) { st.nextToken(); int z(int)st.nval; st.nextToken(); int x(int)st.nval; st.nextToken(); int y(int)st.nval; if (z 1) { union(x,y); } else if (z2) { int res Find(x); int res1 Find(y); out.println(res1res?Y:N); } } } public static void DSU(int[] boss) { for (int i 0; i boss.length; i) { boss[i] i; } } public static int Find(int x) { if (x boss[x]) { return x; } else { return boss[x] Find(boss[x]); } } public static void union(int x, int y) { int rootx Find(x); int rooty Find(y); if (rooty ! rootx) { boss[rootx] rooty; } } }