059拓扑排序

import java.util.ArrayList;

class Solution {
/**
* 找到所有课程的正确学习顺序。
* 这个问题可以建模为一个有向无环图（DAG）的拓扑排序问题。
*
* @param numCourses 课程总数
* @param prerequisites 先决条件数组，prerequisites[i] = [ai, bi] 表示学习课程 ai 之前必须先学习课程 bi
* @return 课程的有效学习顺序，如果不存在（图中存在环），则返回一个空数组
*/
public int[] findOrder(int numCourses, int[][] prerequisites) {
// 1. 建立邻接表（图）和入度表
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
int[] inDegree = new int[numCourses];

        // 遍历所有先决条件，构建图并计算每个节点的入度
        for (int[] edge : prerequisites) {
            int toCourse = edge[0]; // 依赖的课程
            int fromCourse = edge[1]; // 前置课程
            
            // 添加有向边: fromCourse -> toCourse
            graph.get(fromCourse).add(toCourse);
            
            // 增加 toCourse 的入度
            inDegree[toCourse]++;
        }

        // 2. 将所有入度为0的节点加入队列
        int[] queue = new int[numCourses];
        int front = 0; // 队列头部指针
        int rear = 0;  // 队列尾部指针

        // 遍历所有课程，将入度为0的课程加入队列
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue[rear++] = i;
            }
        }

        // 3. 执行拓扑排序（Kahn's 算法）
        int count = 0; // 记录已学习的课程数
        while (front < rear) {
            int currentCourse = queue[front++]; // 移除队列头部的课程

            count++; // 课程数加1
            
            // 遍历当前课程的所有邻居（即依赖于它的课程）
            for (int nextCourse : graph.get(currentCourse)) {
                // 将邻居的入度减1
                inDegree[nextCourse]--;
                
                // 如果邻居的入度变为0，说明它的所有前置课程都已学习，可以加入队列
                if (inDegree[nextCourse] == 0) {
                    queue[rear++] = nextCourse;
                }
            }
        }
        
        // 4. 验证结果
        // 如果已学习的课程数等于总课程数，说明不存在环，返回学习顺序
        // 否则，图中存在环，无法完成所有课程，返回空数组
        return count == numCourses ? queue : new int[0];
    }
}

class Solution {
    public String alienOrder(String[] words) {
        // 创建一个入度数组，用于存储每个字母的入度。
        // 入度代表一个字母有多少个“前置”字母，即有多少个字母必须排在它前面。
        // 数组大小为26，代表'a'到'z'。
        int []ind = new int[26];
        // 将入度数组初始化为-1。
        // -1表示该字母未出现在任何单词中。
        Arrays.fill(ind, -1);
        
        // 第一次遍历所有单词，找到所有出现过的字母，并将其入度初始化为0。
        for(String w : words){
            for(int i = 0; i < w.length(); i++){
                // 确保只处理存在于单词中的字母。
                // 如果一个字母存在，其入度为0，表示它还没有已知的“前置”字母。
                ind[w.charAt(i) - 'a'] = 0;
            }
        }
        
        // 建图：使用邻接表来表示字母之间的依赖关系。
        // 例如，如果a在b之前，那么从a到b有一条有向边。
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for(int i = 0; i < 26; i++){
            graph.add(new ArrayList<>());
        }
        
        // 遍历相邻的单词对，构建图和计算入度。
        // 如果 words[i] = "abc", words[i+1] = "abd"，
        // 那么 'c' 必须在 'd' 之前，这就是一个依赖关系。
        for(int i = 0, j, len; i < words.length - 1; i++){
            String cur = words[i];
            String next = words[i + 1];
            j = 0;
            // 只需要遍历两个单词中较短的那个的长度。
            len = Math.min(cur.length(), next.length());
            for(; j < len; j++){
                // 找到第一个不相同的字母。
                if(cur.charAt(j) != next.charAt(j)){
                    // 建立从当前字母到下一个字母的边。
                    // 例如，从'a'到'b'。
                    graph.get(cur.charAt(j) - 'a').add(next.charAt(j) - 'a');
                    // 增加下一个字母的入度。
                    ind[next.charAt(j) - 'a']++;
                    break;
                }
            }
            // 处理特殊情况：如果"abc"排在"ab"前面，这是不合法的。
            // 例如，["abc", "ab"]，这表明存在一个循环依赖，无法确定顺序。
            if(j < cur.length() && j == next.length()){
                return "";
            }
        }
        
        // 创建一个队列用于拓扑排序，使用数组模拟。
        int []queue = new int [26];
        int l = 0, r = 0; // l为队头指针，r为队尾指针。
        int kinds = 0; // 记录所有出现过的字母数量。
        
        // 初始化队列，将所有入度为0的字母（即没有前置字母的字母）加入队列。
        // 只有入度不为-1的字母才算作有效字母。
        for(int i = 0; i < 26; i++){
            if(ind[i] != -1){
                kinds++;
            }
            if(ind[i] == 0){
                queue[r++] = i;
            }
        }
        
        // 使用StringBuilder来构建结果字符串。
        StringBuilder ans = new StringBuilder();
        
        // 拓扑排序主循环。
        while(l < r){
            // 出队一个入度为0的字母。
            int cur = queue[l++];
            // 将该字母添加到结果字符串中。
            ans.append((char)(cur + 'a'));
            
            // 遍历当前字母的所有“邻居”。
            for(int next : graph.get(cur)){
                // 将邻居的入度减1。
                ind[next]--;
                // 如果邻居的入度变为0，表示其所有前置字母都已处理，
                // 此时将其加入队列。
                if(ind[next] == 0){
                    queue[r++] = next;
                }
            }
        }
        
        // 检查结果是否完整。如果结果字符串的长度等于所有出现过的字母数量，
        // 则表示所有字母都已成功排序，返回结果。
        // 否则，说明图中存在环（即循环依赖），无法确定唯一顺序，返回空字符串。
        return ans.length() == kinds ? ans.toString() : "";
    }
}