使用 BFS 实现拓扑排序

210. 课程表 II

题目链接：210. 课程表 II

题目描述：

题目解析：

• 给我们一个 int 数，代表 id 为 0 到 numCourses 的课程
• 给我们一个 prerequisites 数组，其中从后往前代表学习顺序
• 让我们看能否排课，将课程学完，必须保证学习顺序，返回学习的顺序，不行就返回空数组

解题思路：

• 我们使用二维数组 List，来表示图，每一个下标对应的一维数组，表示该点指向的点
• 我们遍历一次 prerequisites 数组，将最后的 n-1 列的值当成点，其余入该点对应的一维数组。除了 n-1 列，其余对应的入度数组对应下标值加一
• 在进行一次 BFS 即可，每次出的点都进入结果数组
• 注意事项：
  • 我们先将结果数组初始化为 0 到 numCourses-1，prerequisites 可以是 [] 数组时直接就返回
  • 当最后执行完，我们使用一个计数器 lep 来标记进入结果数组的元素，最后只需要比较 lep 与 numCourses 是否一样，一样返回结果数组，不一样返回空数组

解题代码：

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 结果数组
        int[] ret = new int[numCourses];
        for (int i = 0; i < numCourses; i++) ret[i] = i;
        
        int m = prerequisites.length;
        if (m == 0) return ret;
        
        int n = prerequisites[0].length;
        Queue<Integer> queue = new LinkedList<>();
        // 标记数组
        boolean[] flag = new boolean[numCourses];
        // 入度数组
        int[] in = new int[numCourses];
        // 建图
        List<List<Integer>> edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }
        
        // 记录入度，初始图
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n - 1; j++) {
                edges.get(prerequisites[i][n - 1]).add(prerequisites[i][j]);
                in[prerequisites[i][j]]++;
            }
        }
        
        // 入度为 0 的点入队
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) {
                flag[i] = true;
                queue.add(i);
            }
        }
        
        // BFS
        int lep = 0;
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            ret[lep++] = tmp;
            // 删去该点出的边
            for (int i = 0; i < edges.get(tmp).size(); i++) {
                in[edges.get(tmp).get(i)]--;
            }
            // 入队
            for (int i = 0; i < numCourses; i++) {
                if (in[i] == 0 && !flag[i]) {
                    queue.add(i);
                    flag[i] = true;
                }
            }
        }
        
        if (lep != numCourses) return new int[]{};
        return ret;
    }
}

LCR 114. 火星词典

题目链接：LCR 114. 火星词典

题目描述：

题目解析：

• 给我们一个字符串数组 words
• 两个字符串对比来得出字母顺序，两个字符串第一个不相同的字母的顺序等于两个字符串在数组中的顺序，如示例一第一个字符串'wrt'和第二个字符串'wrf'得出的字母顺序就是 t->f
• 将所有的字符两两对比，得出字母顺序，不能得出线性顺序就返回空字符串''

解题思路：

• 两层 for 循环，先搜索两个规则导致的排序结果建立图，例如示例一就建立这个图
• 根据图拓扑排序，得出结论
• 细节问题：abc 和 ab，并且 abc 在数组中位于 ab 前面，这种是不合法的

解题代码：

class Solution {
    // 图
    Map<Character, Set<Character>> edges = new HashMap<>();
    // 入度
    Map<Character, Integer> in = new HashMap<>();
    // 标记有没有 abc ab 这种不合法
    boolean flag;

    public String alienOrder(String[] words) {
        // 初始化入度
        for (String s : words) {
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                in.put(ch, 0);
            }
        }
        
        // 建图
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                add(words[i], words[j]);
                if (flag == true) return "";
            }
        }
        
        // 拓扑排序初始化
        Queue<Character> queue = new LinkedList<>();
        for (char ch : in.keySet()) {
            if (in.get(ch) == 0) queue.add(ch);
        }
        
        // BFS
        StringBuffer ret = new StringBuffer();
        while (!queue.isEmpty()) {
            char tmp = queue.poll();
            ret.append(tmp);
            if (!edges.containsKey(tmp)) continue;
            for (char ch : edges.get(tmp)) {
                in.put(ch, in.get(ch) - 1);
                if (in.get(ch) == 0) {
                    queue.add(ch);
                }
            }
        }
        
        for (char ch : in.keySet()) {
            if (in.get(ch) != 0) return "";
        }
        return ret.toString();
    }

    public void add(String a, String b) {
        int i = 0;
        int n = Math.min(a.length(), b.length());
        for (; i < n; i++) {
            char ch1 = a.charAt(i);
            char ch2 = b.charAt(i);
            if (ch1 != ch2) {
                // ch1 -> ch2
                if (!edges.containsKey(ch1)) {
                    edges.put(ch1, new HashSet<>());
                }
                if (!edges.get(ch1).contains(ch2)) {
                    edges.get(ch1).add(ch2);
                    in.put(ch2, in.get(ch2) + 1);
                }
                break;
            }
        }
        if (i == b.length() && a.length() > i) flag = true;
    }
}