Trie 与图建模模板：前缀匹配和邻接关系的通用起手式#

class Trie {
    class TrieNode {
        TrieNode[] children = new TrieNode[26]; // 26 个小写字母分支
        boolean isEnd; // 标记是否为某个完整单词的结尾
    }

    private TrieNode root; // Trie 根节点（不存具体字符）

    public Trie() {
        root = new TrieNode(); // 初始化空前缀树
    }

    public void insert(String word) {
        TrieNode current = root; // 从根开始沿字符路径向下走
        for (char currentChar : word.toCharArray()) { // 逐字符插入
            int index = currentChar - 'a'; // 字符映射到 0~25 的数组下标
            if (current.children[index] == null) { // 若该分支不存在则新建节点
                current.children[index] = new TrieNode();
            }
            current = current.children[index]; // 移动到下一层
        }
        current.isEnd = true; // 完整单词结束位置打标记
    }

    public boolean search(String word) {
        TrieNode node = findNode(word); // 查找 word 对应路径终点
        return node != null && node.isEnd; // 必须路径存在且是单词终点才算命中
    }

    public boolean startsWith(String prefix) {
        return findNode(prefix) != null; // 只要前缀路径存在即可
    }

    private TrieNode findNode(String text) {
        TrieNode current = root; // 从根开始查找
        for (char currentChar : text.toCharArray()) { // 按字符逐层匹配
            int index = currentChar - 'a'; // 字符转下标
            if (current.children[index] == null) { // 任一分支不存在则查找失败
                return null;
            }
            current = current.children[index]; // 继续向下
        }
        return current; // 返回路径终点节点（可能是前缀终点，不一定是完整单词）
    }
}

class Solution {
    public List<List<Integer>> buildGraph(int nodeCount, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>(); // 邻接表：graph[u] 存 u 指向的所有节点
        for (int node = 0; node < nodeCount; node++) { // 为每个节点创建邻接列表
            graph.add(new ArrayList<>());
        }

        for (int[] edge : edges) { // 遍历先修关系边
            int from = edge[1]; // 前置课程/起点节点
            int to = edge[0]; // 后续课程/终点节点
            graph.get(from).add(to); // 建立有向边 from -> to
        }

        return graph; // 返回构建好的图结构
    }
}

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>(); // 邻接表
        int[] indegree = new int[numCourses]; // 入度数组：每门课还剩多少前置条件

        for (int course = 0; course < numCourses; course++) { // 初始化图容器
            graph.add(new ArrayList<>());
        }

        for (int[] prerequisite : prerequisites) { // 建图并统计入度
            int next = prerequisite[0]; // 要学习的课程
            int prev = prerequisite[1]; // 它依赖的前置课程
            graph.get(prev).add(next); // prev -> next
            indegree[next]++; // next 入度 +1
        }

        Queue<Integer> queue = new LinkedList<>(); // 拓扑排序队列：存当前可学课程（入度为 0）
        for (int course = 0; course < numCourses; course++) {
            if (indegree[course] == 0) { // 无前置依赖可直接学习
                queue.offer(course);
            }
        }

        int finished = 0; // 已成功学习课程计数
        while (!queue.isEmpty()) { // 不断学习当前可学课程
            int current = queue.poll(); // 取一门可学课程
            finished++; // 学完课程数 +1

            for (int next : graph.get(current)) { // 当前课程的后续课程
                indegree[next]--; // 消耗一个前置条件
                if (indegree[next] == 0) { // 若后续课程已无依赖，则可入队学习
                    queue.offer(next);
                }
            }
        }

        return finished == numCourses; // 全部课程都学完则无环，可完成
    }
}