题目描述
在数据链路中，每个设备都有数据流入设备和流出设备，流入流出关系通过一个表格记录，请根据给出的记录表，计算出设备所属链路的最大长度（链路的节点个数）
输入描述：
第1行输入为关系记录的数量 N， N<=100
第2行输入为待计算所属链路的最大长度的设备0
从第3至N+2行输入为关系记录，每一行关系记录按照设备ID，流入设备ID，流出设备ID空格字符分隔。每个设备都有自己的关系记录
输出描述：
对于每组测试数据，输出0所属链路的最大长度
用例1
输入：
4
device1
device1 device2 device3
device2 null device1
device3 device1 device4
device4 device3 null
输出：
4
用例说明：
第一行数据4表示有4条数据关系记录。
第二行数据device1表示需要计算device1的所属链路的最长长度。
第三行device1 device2 device3：设备device1的流入设备有 device2，流出设备有deviec3。
第四行device2 null device1：设备device2没有流入设备，流出设备有device1。
第五行device3 device1 device4：设备device3的流入设备有 device1，流出设备有device4。
第六行device4 device3 null：设备device4的流入设备有device3，没有流出设备。
根据上述信息可以还原出一条链路关系：device2->device1->device3->device4
注：当没有流入设备或者流出设备时，用 null 字符表示。
用例2：
输入：
8
d3
d1 null d2
d2 d1 d3
d2 d1 d5
d2 d1 d4
d3 d2 null
d4 d2 null
d5 d2 d6
d8 d5 null
输出：
3
备注：
一个设备可以属于多个链路，每个设备只有一个流入设备，但每个设备可以有多个流出设备，切各设备组成的链路不存在环路。
解题代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = Integer.parseInt(scanner.nextLine());
String deviceId = scanner.nextLine();
String root = null;
// 键为设备ID，值为流入设备
Map<String, String> registry = new HashMap<>();
for (int i = 0; i < size; i++) {
String line = scanner.nextLine();
String[] record = line.split(" ");
if ("null".equals(record[1])) {
root = record[0];
registry.put(root, null);
} else {
registry.put(record[0], record[1]);
}
// 终点设备
if (!"null".equals(record[2])) {
registry.put(record[2], record[0]);
}
}
Map<String, Integer> maxPathMap = maxPath(registry);
System.out.println(maxPathMap.get(deviceId));
}
public static Map<String, Integer> maxPath(Map<String, String> path) {
Map<String, Integer> result = new HashMap<>();
Set<String> devices = path.keySet();
for (String d : devices) {
// 表示路径长度
int length = 1;
String front = d;
Set<String> deviceInPath = new HashSet<>();
deviceInPath.add(d);
for(;;) {
front = path.get(front);
if (front == null) {
break;
}
deviceInPath.add(front);
length++;
}
// 更新路径中所有节点的最大路径
Integer max;
for (String s : deviceInPath) {
max = result.getOrDefault(s, length);
max = Math.max(max, length);
result.put(s, max);
}
}
return result;
}
}
自编用例：
输入：
1
d1
d1 null null
输出
1