华为OD机试统一考试D卷C卷 - 查找一个有向网络的头节点和

题目描述

给定一个有向图,图中可能包含有环,图使用二维矩阵表示,每一行的第一列表示起始节点,第二列表示终止节点,如 [0, 1] 表示从 0 到 1 的路径。

每个节点用正整数表示。求这个数据的首节点与尾节点,题目给的用例会是一个首节点,但可能存在多个尾节点。同时图中可能含有环。如果图中含有环,返回 [-1]。

说明:入度为0是首节点,出度为0是尾节点。

image-20240121210316419

输入描述

第一行为后续输入的键值对数量N(N ≥ 0)

第二行为2N个数字。每两个为一个起点,一个终点.

输出描述

输出一行头节点和尾节点。如果有多个尾节点,按从小到大的顺序输出

备注

  • 如果图有环,输出为 -1
  • 所有输入均合法,不会出现不配对的数据

用例1

输入

4
0 1 0 2 1 2 2 3

输出

0 3

说明

image-20240121210602591

用例2

输入

2
0 1 0 2

输出

0 1 2

说明

image-20240121210613459

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#
全部评论
感觉这题还是可以写出来的
点赞 回复 分享
发布于 2023-03-26 18:51 湖南
这是2023年的真题么
点赞 回复 分享
发布于 2023-03-26 19:00 广东
m
点赞 回复 分享
发布于 2023-12-13 20:24 江苏
getMaxNum 函数的时间复杂度是多少
点赞 回复 分享
发布于 2023-12-13 20:29 江苏
有没有更节省空间的方法实现 getMaxNum 函数,不使用两个 HashMap?
点赞 回复 分享
发布于 2023-12-13 20:30 江苏
如果输入字符串的长度非常大,这段代码的性能表现如何?
点赞 回复 分享
发布于 2023-12-13 20:30 江苏
是否可以使用数组或其他数据结构来优化 getMaxNum 函数中的栈实现?
点赞 回复 分享
发布于 2023-12-13 20:30 江苏
代码中是否有重复计算或可以优化的部分,以减少运行时间?
点赞 回复 分享
发布于 2023-12-13 20:30 江苏

相关推荐

世界上最难的事情是,长大以后的你还在坚持着实现小时候的梦想;而更难的事情则是,你真的实现了小时候的梦想。&nbsp;10&nbsp;年前的那个孩子怎么也不会想到,10&nbsp;年后的他自己竟然真的成为了他梦想中的那个样子......&nbsp;启航&nbsp;不知道为什么,从小就对计算机这么一个冰冷的东西情有独钟:我热衷于探索&nbsp;Windows&nbsp;XP&nbsp;控制面板中的每一个选项,与&nbsp;Windows&nbsp;搜索的吉祥物&nbsp;Rover&nbsp;做朋友,研究光驱和&nbsp;3.5&nbsp;软盘驱动器(是的,3.5&nbsp;软盘!)的使用方式&nbsp;——&nbsp;即使在那个计算机还没有普遍连上网的时代,我依然愿意探索计算机中的每一个角落。&nbsp;当然,这可能和我喜欢玩计算机游戏有关,在那个网络并不发达,移动通信...
在摸鱼的香菇很想退休:感觉佬的经历是我曾经想过的 我最开始想学计算机是因为我想写游戏脚本 不过后来上大学走偏了去打竞赛了 不过算是找到另外一个爱好了 从结果来看感觉还是学历加非科班吃了亏 不过现在形式不好 读研也不一定能有更好的结果 还是祝愿佬拿到更多更好的offer吧 感觉你真的很优秀
点赞 评论 收藏
分享
扭转乾坤_:现在企业都是学华为,一直通过丢池子里,最后捞
点赞 评论 收藏
分享
秋招倒计时了,有没有一起组队捡漏的?
牛客965593684号:我倒是觉得捡漏机会不多,现在大厂都精得很,超发一大堆offer,还是等春招吧
点赞 评论 收藏
分享
2 5 评论
分享
牛客网
牛客企业服务