题目描述

给定一个有向图，图中可能包含有环，图使用二维矩阵表示，每一行的第一列表示起始节点，第二列表示终止节点，如 [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;
    }
}