AcWing 1498. 最深的根-java-并查集+dfs
原题链接
中等
作者:
Astarion
,
2021-03-10 16:14:23
,
所有人可见
,
阅读 455
import java.io.*;
import java.util.*;
class Main {
static InputStreamReader isr = new InputStreamReader(System.in);
static BufferedReader in = new BufferedReader(isr);
static OutputStreamWriter osw = new OutputStreamWriter(System.out);
static BufferedWriter out = new BufferedWriter(osw);
static String[] strs;
static final int N = 20010;
static int n, idx;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static boolean[] flag = new boolean[N];
//使用并查集判断是否有环
static int cnt = 1;
static int[] p = new int[N];
static {
Arrays.fill(h, -1);
for (int i = 0; i < N; i++) p[i] = i;
}
//记录各个root对应的高度
static List<Integer> maxId = new ArrayList<>();
static int find(int i) {
if (p[i] != i) p[i] = find(p[i]);
return p[i];
}
static void insert(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
e[idx] = a;
ne[idx] = h[b];
h[b] = idx++;
int pa = find(a);
int pb = find(b);
//未在同一颗树,合并
if (pa != pb) p[pa] = pb;
//若在同一棵树种加入新的边,则产生新的连通分量
else cnt++;
}
//dfs求树的高度
static int dfs(int root) {
flag[root] = true;
int height = 0;
for (int i = h[root]; i != -1; i = ne[i]) {
if (flag[e[i]]) continue;
height = Math.max(dfs(e[i]) + 1, height);
}
return height;
}
public static void main(String[] args) throws IOException {
n = Integer.parseInt(in.readLine());
for (int i = 0; i < n - 1; i++) {
strs = in.readLine().split(" ");
int a = Integer.parseInt(strs[0]);
int b = Integer.parseInt(strs[1]);
insert(a, b);
}
//有多个连通分量
if (cnt > 1) {
out.write(String.format("Error: %d components", cnt));
out.flush();
return;
}
//是一棵树,对每个root节点求树高
int maxH = 0;
for (int i = 1; i <= n; i++) {
//flag标记是否已查找过该节点
Arrays.fill(flag, false);
int temp = dfs(i);
if (temp > maxH) {
maxId.clear();
maxId.add(i);
maxH = temp;
} else if (temp == maxH) maxId.add(i);
}
for (int i : maxId) out.write(i + "\n");
in.close();
isr.close();
out.flush();
out.close();
osw.close();
}
}
加油!java的同学!
加油!