华为OD机试统一考试D卷C卷 - 查找一个有向网络的头节点和
题目描述
给定一个有向图,图中可能包含有环,图使用二维矩阵表示,每一行的第一列表示起始节点,第二列表示终止节点,如 [0, 1] 表示从 0 到 1 的路径。
每个节点用正整数表示。求这个数据的首节点与尾节点,题目给的用例会是一个首节点,但可能存在多个尾节点。同时图中可能含有环。如果图中含有环,返回 [-1]。
说明:入度为0是首节点,出度为0是尾节点。
输入描述
第一行为后续输入的键值对数量N(N ≥ 0)
第二行为2N个数字。每两个为一个起点,一个终点.
输出描述
输出一行头节点和尾节点。如果有多个尾节点,按从小到大的顺序输出
备注
- 如果图有环,输出为 -1
- 所有输入均合法,不会出现不配对的数据
用例1
输入
4
0 1 0 2 1 2 2 3
输出
0 3
说明
用例2
输入
2
0 1 0 2
输出
0 1 2
说明
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取边的数量
int N = scanner.nextInt();
// 存储所有边的数组
int[] edges = new int[2 * N];
for (int i = 0; i < 2 * N; i++) {
// 读取每条边的起点和终点
edges[i] = scanner.nextInt();
}
// 找出起点和终点
int[] result = findStartAndEndNodes(edges);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < result.length; i++) {
// 构建输出字符串
sb.append(result[i]);
if (i < result.length - 1) {
sb.append(" ");
}
}
// 打印结果
System.out.println(sb.toString());
}
// 方法:找出起点和终点
private static int[] findStartAndEndNodes(int[] edges) {
// 存储每个节点的入度
Map<Integer, Integer> inDegree = new HashMap<>();
// 存储每个节点的出度
Map<Integer, Integer> outDegree = new HashMap<>();
// 存储所有节点
Set<Integer> nodes = new HashSet<>();
for (int i = 0; i < edges.length; i += 2) {
int start = edges[i];
int end = edges[i + 1];
// 添加节点
nodes.add(start);
nodes.add(end);
// 计算入度和出度
inDegree.put(end, inDegree.getOrDefault(end, 0) + 1);
outDegree.put(start, outDegree.getOrDefault(start, 0) + 1);
}
// 检查是否有环
if (hasCycle(nodes, edges)) {
return new int[]{-1};
}
// 找出终点
List<Integer> endNodes = new ArrayList<>();
// 起点
int startNode = -1;
for (int node : nodes) {
// 如果一个节点没有入度,它是起点
if (!inDegree.containsKey(node)) {
startNode = node;
}
// 如果一个节点没有出度,它是终点
if (!outDegree.containsKey(node)) {
endNodes.add(node);
}
}
// 构建结果数组
int[] result = new int[endNodes.size() + 1];
result[0] = startNode;
for (int i = 0; i < endNodes.size(); i++) {
result[i + 1] = endNodes.get(i);
}
return result;
}
// 方法:检查是否有环
private static boolean hasCycle(Set<Integer> nodes, int[] edges) {
// 构建图
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int node : nodes) {
graph.put(node, new ArrayList<>());
}
for (int i = 0; i < edges.length; i += 2) {
graph.get(edges[i]).add(edges[i + 1]);
}
// 记录已访问和回溯栈的节点
Set<Integer> visited = new HashSet<>();
Set<Integer> recStack = new HashSet<>();
// 检查每个节点是否有环
for (int node : nodes) {
if (detectCycle(graph, node, visited, recStack)) {
return true;
}
}
return false;
}
// 辅助方法:递归检查环
private static boolean detectCycle(Map<Integer, List<Integer>> graph, int node,
Set<Integer> visited, Set<Integer> recStack) {
// 如果节点在回溯栈中,表示有环
if (recStack.contains(node)) {
return true;
}
// 如果已经访问过,不需要再次访问
if (visited.contains(node)) {
return false;
}
// 标记节点为已访问,并加入回溯栈
visited.add(node);
recStack.add(node);
// 检查相邻节点
List<Integer> neighbors = graph.get(node);
for (int neighbor : neighbors) {
if (detectCycle(graph, neighbor, visited, recStack)) {
return true;
}
}
// 从回溯栈中移除节点
recStack.remove(node);
return false;
}
}
#华为机试,emo了##华为od#