题解 | #星际航线规划#

GPT: 我们使用邻接表来表示图。然后，我们使用深度优先搜索来检测是否存在环。在搜索过程中，我们使用两个布尔数组来跟踪访问过的节点和当前路径上的节点。如果我们在搜索过程中遇到一个已经访问过的节点，并且它在当前路径上，那么就说明存在环。如果搜索完所有的节点都没有发现环，那么就说明可以访问所有的星球。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 输入星球的数量
        int m = scanner.nextInt(); // 输入航线的数量
        List<Integer>[] graph = new List[n]; // 创建邻接表来表示图
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>(); // 初始化邻接表
        }
        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt() - 1; // 输入星球x
            int y = scanner.nextInt() - 1; // 输入星球y
            graph[x].add(y); // 在邻接表中添加一条从星球x到星球y的边
        }
        boolean[] visited = new boolean[n]; // 创建布尔数组来跟踪访问过的节点
        boolean[] onStack = new boolean[n]; // 创建布尔数组来跟踪当前路径上的节点
        for (int i = 0; i < n; i++) {
            if (!visited[i]) { // 如果节点i没有被访问过
                if (hasCycle(graph, visited, onStack, i)) { // 检测是否存在环
                    System.out.println("No"); // 如果存在环，输出"No"
                    return;
                }
            }
        }
        System.out.println("Yes"); // 如果不存在环，输出"Yes"
    }

    private static boolean hasCycle(List<Integer>[] graph, boolean[] visited, boolean[] onStack, int v) {
        visited[v] = true; // 标记节点v为已访问
        onStack[v] = true; // 将节点v添加到当前路径上
        for (int w : graph[v]) { // 遍历节点v的所有邻居
            if (!visited[w]) { // 如果邻居w没有被访问过
                if (hasCycle(graph, visited, onStack, w)) { // 递归检测是否存在环
                    return true; // 如果存在环，返回true
                }
            } else if (onStack[w]) { // 如果邻居w已经在当前路径上
                return true; // 说明存在环，返回true
            }
        }
        onStack[v] = false; // 将节点v从当前路径上移除
        return false; // 不存在环，返回false
    }
}