AcWing 238. 银河英雄传说---Java
原题链接
简单
作者:
夏日的小提琴
,
2021-12-17 17:23:42
,
所有人可见
,
阅读 331
import java.io.*;
public class Main {
static int N = 30010;//战舰的最大数量
static int t;//指令个数
static int[] p = new int[N];//存储每艘战舰的父节点
static int[] d = new int[N];//存储每艘战舰到父节点的距离
static int[] size = new int[N];//存储每列战舰的个数
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
t = Integer.parseInt(reader.readLine());
for (int i = 1; i < N; i++) {
p[i] = i;//每个战舰初始父节点是自己
size[i] = 1;//每个列初始只有一艘战舰,所以个数是1
}
while (t-- > 0) {
String[] str = reader.readLine().split(" ");
String ch = str[0];
int a = Integer.parseInt(str[1]);
int b = Integer.parseInt(str[2]);
int fa = find(a);
int fb = find(b);
if (ch.equals("M")) {
if (fa != fb) {
d[fa] = size[fb];//小技巧,只需要更新加到后面的列的根结点战舰的距离,这样相当于后面的战舰到新的根节点的距离都加了size[fb]
size[fb] += size[fa];//更新合并后该列的总个数
p[fa] = fb;//a列接到b列后面
}
} else {
if (fa != fb) {//不在一列则输出-1
writer.write("-1\n");
} else {
if (a == b) {
writer.write("0\n");//如果是同一艘战舰,则之间间隔的数目为0
} else {
int x = Math.abs(d[a] - d[b]) - 1;
writer.write(x + "\n");
}
}
}
}
writer.flush();
writer.close();
reader.close();
}
//并查集查找根节点 + 路径压缩,同时还维护每个节点到根节点的距离
public static int find(int x) {
if (p[x] != x) {
int temp = find(p[x]);
d[x] += d[p[x]];
p[x] = temp;
}
return p[x];
}
}