连通块中点的数量、堆箱子（4星）

连通块中点的数量问题描述给定一个初始包含 nn 个点00 条边的图。第 ii 个点的编号为 ii。(1≤i≤n)(1≤i≤n)现在要进行 mm 次操作操作共三种C a b在点 aa 与点 bb 之间连一条边a,ba,b 可能相等。Q1 a b询问点 aa 与点 bb 是否在一个连通块中a,ba,b 可能相等。Q2 a询问点 aa 所在连通块中点的数量。输入格式第一行输入两个正整数 n,mn,m。(1≤n,m≤105)(1≤n,m≤105)接下来 mm 行每行输入包含一种操作。(1≤a,b≤n)(1≤a,b≤n)输出格式对于查询Q1 a b若 a,ba,b 在一个连通块中输出Yes否则输出No。对于查询Q2 a输出点 aa 所在连通块中点的数量。样例输入5 7 C 1 2 Q1 1 2 Q2 1 C 2 5 Q2 5 Q1 1 1 Q1 2 3样例输出Yes 2 3 Yes Noimport java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N100010,mod998244353; static int size[]new int[N]; static int p[]new int[N]; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); int nInteger.parseInt(st.nextToken()),mInteger.parseInt(st.nextToken()); for (int i 1; i n; i) { p[i]i; size[i]1; } for (int i 0; i m; i) { stnew StringTokenizer(br.readLine()); // C a b在点 a 与点 b 之间连一条边(a,b) 可能相等。 // Q1 a b询问点 a 与点 b 是否在一个连通块中(a,b) 可能相等。 // Q2 a询问点 a 所在连通块中点的数量。 String opest.nextToken(); int aInteger.parseInt(st.nextToken()); if(st.hasMoreTokens()){ int bInteger.parseInt(st.nextToken()); if(C.equals(ope)){ if(ab)continue; union(a,b); }else{ if(ab){ bw.write(Yes\n); }else{ if(find(a)find(b)){ bw.write(Yes\n); }else{ bw.write(No\n); } } } }else{ int fafind(a); bw.write(size[fa]\n); } } br.close(); bw.flush(); bw.close(); } static void union(int a,int b){ afind(a);bfind(b); if(a!b){ p[a]b; size[b]size[a]; } } static int find(int i){ if(i!p[i]){ p[i]find(p[i]); } return p[i]; } }堆箱子4星问题描述暑假到了小蓝打完蓝桥杯去工厂兼职成为了工厂里的搬运工工厂里面初始有 nn 个箱子平铺在地面上每个箱子都有一个编号分别是 1,2,3...n1,2,3...n。由于小蓝喜欢算法竞赛他想到了一个问题。现在有 22 种操作具体操作如下1 a b11 号操作将 aa 位置所在的所有箱子搬到 bb 位置所在的箱子上面已经在相同位置的箱子不能进行此操作。2 a22 号操作查询 aa 位置下有多少个箱子。现在小蓝有 qq 次操作对于每次操作 22 你需要输出结果。输入格式第一行二个整数 n,qn,q 表示箱子的数量和操作次数。接下来 qq 行每行输入代表一个具体操作。输出格式对所有的操作 22 输出其结果。样例输入6 6 1 4 2 2 2 2 4 1 2 3 2 2 2 4样例输出0 1 1 2在第一次操作后44 下面是 22 号箱子。在第二次操作后44 下面是 22 号箱子22 下面是 33 号箱子。评测数据规模1≤n≤3×104,1≤q≤1051≤n≤3×104,1≤q≤105。import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N3*10010; static int size[]new int[N];//该根节点对应树有多少节点 最下面的节点是根节点 static int p[]new int[N];//父节点 static int d[]new int[N];//该位置下面有多少个箱子 也就是答案 static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); int nInteger.parseInt(st.nextToken()),qInteger.parseInt(st.nextToken()); for (int i 1; i n; i) { p[i]i; size[i]1; } for (int i 0; i q; i) { stnew StringTokenizer(br.readLine()); int opeInteger.parseInt(st.nextToken()); if(ope1){ int aInteger.parseInt(st.nextToken()),bInteger.parseInt(st.nextToken()); //a位置所在的所有箱子搬到b 位置所在的箱子上面 //我们只更新a原来的父节点pa的d[fa] 其子节点先不用跟新 我们后续只需要 d[i]d[i]d[p[i]]; //当然 p[i]也可能没有被更新过 所有我们要在find里更新 if(ab)continue; union(a,b); }else{ int aInteger.parseInt(st.nextToken()); find(a); bw.write(d[a]\n); } } br.close(); bw.flush(); bw.close(); } static void union(int a,int b){ afind(a);bfind(b); if(a!b){ d[a]size[b]; p[a]b; size[b]size[a]; } } static int find(int i){ if(i!p[i]){ int vfind(p[i]); d[i]d[i]d[p[i]]; p[i]v; } return p[i]; } }