查找一个有向网络的头节点和尾节点

一、题目描述给定一个有向图图中可能包含有环有向边用两个节点表示。第一个整数表示起始节点第二个整数表示终止节点如0 1表示存在从0到1的路径。每个节点用正整数表示求这个数据的头节点与尾节点题目给的用例会是一个头节点但可能存在多个尾节点。同时图中可能含有环如果图中含有环返回-1。说明入度为0是头节点出度为0是尾节点二、输入输出描述输入描述第一行整数N边的数量N ≥ 0第二行2N个整数每两个为一组表示一条有向边第一个为起点第二个为终点所有输入均合法不会出现不配对的数据输出描述存在环输出-1无环输出头节点和尾节点如果有多个尾节点按从大到小的顺序输出。三、示例输入41 2 1 3 2 4 3 4输出1 4说明图的边为1→2、1→3、2→4、3→4入度为 0 的节点1头节点出度为 0 的节点4尾节点无环输出1 4。输入31 2 2 3 3 1输出-1说明存在环1→2→3→1输出-1。四、解题思路1. 核心思想先通过拓扑排序Kahn 算法检测图是否为有向无环图DAG若存在环则直接输出 - 1若为 DAG再利用 “入度 / 出度” 的特征找到唯一头节点入度 0和所有尾节点出度 0最后将尾节点降序排序后输出。核心是 “先验环后找节点”拓扑排序既完成了环检测也为后续节点查找保留了入度 / 出度信息。2. 问题本质分析该问题是有向图的环检测 特殊节点查找核心特征如下输入一组有向边需先构建图结构约束条件仅当图为 DAG 时才存在唯一头节点入度 0和若干尾节点出度 0核心目标检测图是否有环无环时找到头节点和降序排序的尾节点关键原理有向环的特征拓扑排序无法处理完所有节点环内节点入度永远无法为 0DAG 的头节点入度为 0无节点指向它尾节点出度为 0它不指向任何节点。3. 核心逻辑图构建通过邻接表、入度表、出度表完整描述图的结构为后续操作提供数据支撑环检测Kahn 算法入度为 0 的节点入队逐层处理处理节点时其邻接节点入度 - 1新入度为 0 的节点入队若处理节点数 总节点数判定有环节点查找头节点遍历所有节点找到入度为 0 的节点题目保证唯一尾节点遍历所有节点收集出度为 0 的节点并降序排序结果输出有环输出 - 1无环按格式输出头节点 降序尾节点。4. 步骤拆解输入处理与图构建读取边数 N 和 2*N 个节点值按每两个一组解析为有向边构建邻接表记录出边、入度表记录被指向次数、出度表记录指向次数并收集所有节点拓扑排序检测环初始化队列所有入度为 0 的节点入队处理队列取出节点→处理数 1→邻接节点入度 - 1→新入度 0 的节点入队环判断若处理数 总节点数输出 - 1 并终止查找头尾节点头节点遍历节点找到入度为 0 的节点尾节点遍历节点收集出度为 0 的节点降序排序结果输出拼接头节点和降序尾节点按 “头 尾 1 尾 2 ...” 格式输出。五、代码实现import java.util.*; public class GraphHeadTailFinder { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 1. 读取输入 int N scanner.nextInt(); // 边的数量 scanner.nextLine(); // 换行符 int[] edges new int[2 * N]; for (int i 0; i 2 * N; i) { edges[i] scanner.nextInt(); } // 2. 数据初始化邻接表、入度、出度、总节点集合 MapInteger, ListInteger adj new HashMap(); // 邻接表 MapInteger, Integer inDegree new HashMap(); // 入度 MapInteger, Integer outDegree new HashMap(); // 出度 SetInteger allNodes new HashSet(); // 所有节点 // 3. 构建图 for (int i 0; i edges.length; i 2) { int from edges[i]; int to edges[i 1]; // 维护邻接表 adj.computeIfAbsent(from, k - new ArrayList()).add(to); // 维护总节点集合 allNodes.add(from); allNodes.add(to); // 维护入度to节点入度1 inDegree.put(to, inDegree.getOrDefault(to, 0) 1); // 维护出度from节点出度1 outDegree.put(from, outDegree.getOrDefault(from, 0) 1); // 初始化入度/出度为0的节点避免后续空指针 inDegree.putIfAbsent(from, 0); outDegree.putIfAbsent(to, 0); } // 4. 拓扑排序检测环Kahn算法 QueueInteger queue new LinkedList(); // 入度为0的节点入队 for (int node : allNodes) { if (inDegree.get(node) 0) { queue.offer(node); } } int processed 0; // 拓扑排序处理的节点数 while (!queue.isEmpty()) { int curr queue.poll(); processed; // 遍历当前节点的邻接节点入度-1 for (int next : adj.getOrDefault(curr, new ArrayList())) { inDegree.put(next, inDegree.get(next) - 1); if (inDegree.get(next) 0) { queue.offer(next); } } } // 有环处理节点数 总节点数 if (processed allNodes.size()) { System.out.println(-1); scanner.close(); return; } // 5. 无环找头节点和尾节点 // 头节点入度为0的节点题目保证仅1个 int head -1; for (int node : allNodes) { if (inDegree.get(node) 0) { head node; break; } } // 尾节点出度为0的节点收集后降序排序 ListInteger tails new ArrayList(); for (int node : allNodes) { if (outDegree.get(node) 0) { tails.add(node); } } Collections.sort(tails, Collections.reverseOrder()); // 降序排序 // 6. 拼接输出 StringBuilder result new StringBuilder(); result.append(head); for (int tail : tails) { result.append( ).append(tail); } System.out.println(result); scanner.close(); } }