【华为OD-E卷 - 跳格子游戏 100分（python、java、c++、js、c）】

题目

地上共有N个格子，你需要跳完地上所有的格子，但是格子间是有强依赖关系的，跳完前一个格子后，后续的格子才会被开启，格子间的依赖关系由多组steps数组给出，steps[0]表示前一个格子，steps[1]表示steps[0]可以开启的格子:
比如[0,1]表示从跳完第0个格子以后第1个格子就开启了，比如[2,1]，[2,3]表示跳完第2个格子后第1个格子和第3个格子就被开启了。
请你计算是否能由给出的steps数组跳完所有的格子，如果可以输出yes，否则输出no。
说明：
1.你可以从一个格子跳到任意一个开启的格子
2.没有前置依赖条件的格子默认就是开启的
3.如果总数是N，则所有的格子编号为[0,1,2,3…N-1]连续的数组

输入描述

输入一个整数N表示总共有多少个格子，接着输入多组二维数组steps表示所有格子之间的依赖关系

输出描述

如果能按照steps给定的依赖顺序跳完所有的格子输出yes，

否则输出no。

备注

1 ≤ N ＜ 500 step[i].length = 2 0 ≤ step[i][0]，step[i][1] ＜ N

用例

用例一：

输入：

3
0 1
0 2

输出：

yes

用例二：

输入：

2
1 0
0 1

输出：

no

用例三：

输入：

输出：

yes

用例四：

输入：

输出：

yes

python解法

解题思路：
这段代码通过拓扑排序判断是否可以从图的起点遍历到所有节点。问题可以抽象为一个有向图中是否存在拓扑序列，使得所有节点都可以被访问。如果能够完成拓扑排序并且访问的节点数等于图中的节点数，则说明可以跳完所有格子。

以下是解题的主要步骤：

构建图与入度表：

使用 defaultdict 构建邻接表表示有向图。
使用一个列表 in_degree 来记录每个节点的入度（指向该节点的边数）。
初始化队列：

将入度为 0 的节点（没有依赖的节点）加入队列，因为这些节点可以作为起始点开始遍历。
拓扑排序：

使用队列按拓扑顺序遍历图。
每遍历一个节点，将其邻居节点的入度减 1，如果某个邻居节点的入度变为 0，则将其加入队列。
检查结果：

如果拓扑排序访问的节点数等于图中节点总数 N，则说明可以完成所有格子的跳跃。
如果访问的节点数小于 N，则说明存在环，无法完成跳跃

from collections import deque, defaultdict

def can_finish_all_grids(N, steps):
    """
    判断是否可以跳完所有格子。
    
    :param N: 总格子数（节点数）
    :param steps: 每个格子之间的跳跃关系（有向边列表）
    :return: "yes" 如果可以跳完所有格子，否则 "no"
    """
    # 构建图（邻接表）和入度数组
    graph = defaultdict(list)  # 存储邻接关系
    in_degree = [0] * N  # 记录每个节点的入度

    # 遍历跳跃关系，填充图和入度
    for step in steps:
        u, v = step  # u -> v 表示从 u 跳到 v
        graph[u].append(v)  # 添加邻接关系
        in_degree[v] += 1  # 更新 v 的入度

    # 初始化队列，将所有入度为 0 的节点加入队列
    queue = deque()
    for i in range(N):
        if in_degree[i] == 0:
            queue.append(i)

    visited_count = 0  # 记录访问过的节点数

    # 拓扑排序
    while queue:
        node = queue.popleft()  # 从队列中取出一个节点
        visited_count += 1  # 标记节点为已访问

        # 遍历当前节点的所有邻居
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1  # 邻居节点的入度减 1
            if in_degree[neighbor] == 0:  # 如果邻居节点入度变为 0，则加入队列
                queue.append(neighbor)

    # 如果访问的节点数等于总节点数 N，则可以跳完所有格子
    return "yes" if visited_count == N else "no"

# 读取输入
import sys
input = sys.stdin.read
data = input().split()

# 解析输入数据
N = int(data[0])  # 第一个数字是格子总数
steps = []  # 后续每两个数字构成一对跳跃关系
for i in range(1, len(data), 2):
    steps.append([int(data[i]), int(data[i + 1])])

# 计算并输出结果
result = can_finish_all_grids(N, steps)
print(result)

java解法

解题思路
这段代码通过拓扑排序判断是否可以完成所有节点的访问，即是否能够从图中所有起点依次访问所有节点。问题可以抽象为有向无环图（DAG）是否存在完整的拓扑序列。如果可以完成拓扑排序并且访问的节点数等于图中总节点数 n，则说明图中不存在环，所有格子可以跳完。

以下是解题步骤和逻辑：

构建图和入度数组：

使用一个邻接表（List<List> graph）表示有向图的边。
使用数组 inDegree 记录每个节点的入度（被指向的次数）。
初始化队列：

将所有入度为 0 的节点（没有依赖的起始点）加入队列，作为拓扑排序的起点。
拓扑排序：

使用队列按拓扑顺序遍历图。
每遍历一个节点，将其邻居节点的入度减 1，如果某个邻居节点的入度变为 0，则将其加入队列。
检查结果：

如果拓扑排序访问的节点数等于图中总节点数 n，则说明图中不存在环，所有格子可以跳完。
如果访问的节点数小于 n，则说明存在环，无法完成跳跃

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取节点总数 n
        int n = Integer.parseInt(sc.nextLine());

        // 初始化入度数组和邻接表
        int[] inDegree = new int[n]; // 记录每个节点的入度
        List<List<Integer>> graph = new ArrayList<>(); // 邻接表表示有向图

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>()); // 初始化每个节点的邻接表
        }

        // 构建图
        while (sc.hasNextLine()) {
            String line = sc.nextLine(); // 读取输入行
            if (line.isEmpty()) break; // 如果是空行，停止读取
            String[] parts = line.split(" "); // 分割起点和终点
            int from = Integer.parseInt(parts[0]); // 起点
            int to = Integer.parseInt(parts[1]); // 终点
            graph.get(from).add(to); // 添加边 from -> to
            inDegree[to]++; // 更新终点节点的入度
        }

        // 初始化队列，加入所有入度为 0 的节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) { // 如果某节点的入度为 0，加入队列
                queue.add(i);
            }
        }

        // 拓扑排序
        int count = 0; // 记录访问过的节点数
        while (!queue.isEmpty()) {
            int current = queue.poll(); // 从队列中取出一个节点
            count++; // 标记当前节点为已访问
            for (int neighbor : graph.get(current)) { // 遍历当前节点的所有邻居
                inDegree[neighbor]--; // 邻居节点的入度减 1
                if (inDegree[neighbor] == 0) { // 如果邻居节点的入度变为 0，加入队列
                    queue.add(neighbor);
                }
            }
        }

        // 判断是否可以访问所有节点
        System.out.println(count == n ? "yes" : "no"); // 如果访问节点数等于 n，输出 "yes"，否则输出 "no"
    }
}