Leetcode 2392. Build a Matrix With Conditions

[Woodyiiiiiii]

题目给出了节点之间的前后关系，需要找出符合条件的其中一个排序，这种就是拓扑排序。

拓扑排序实现方法：

1. 遍历关系图，用双重数组存储一个节点对应其往后的节点关系
2. 同时维护一个引用次数数组，保存对应每个节点的引用次数
3. 维护一个节点队列，首先遍历引用次数数组，找到次数为0的节点，放入队列中，表示最先确定关系的节点
4. 循环遍历节点队列直至为空，循环中，poll一个节点，找到其对应的子节点，将对应的子节点在引用次数数组中次数-1，如果次数为空，则放入队列中

拓扑排序得到先后顺序队列后：

1. 判断队列大小是否等于所给值，小于的话说明不满足
2. 放入二维数组中

class Solution {
    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        // topological sort
        List<Integer> list1 = buildList(k, rowConditions);
        List<Integer> list2 = buildList(k, colConditions);

        // validate
        if (list1.size() < k || list2.size() < k) {
            return new int[0][0];
        }

        // connection
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < list2.size(); i++) {
            map.put(list2.get(i), i);
        }

        // build matrix
        int[][] matrix = new int[k][k];
        for (int i = 0; i < list1.size(); i++) {
            matrix[i][map.get(list1.get(i))] = list1.get(i) + 1;
        }
        return matrix;
    }
    
    private List<Integer> buildList(int k, int[][] a) {
        int[] cnt = new int[k];
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        List<List<Integer>> list = new ArrayList<>(k);
        for (int i = 0; i < k; ++i) {
            list.add(new ArrayList<>());
        }

        for (int[] b : a) {
            cnt[b[1] - 1]++;
            list.get(b[0] - 1).add(b[1] - 1);
        }

        for (int i = 0; i < k; ++i) {
            if (cnt[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            res.add(cur);
            for (int next : list.get(cur)) {
                cnt[next]--;
                if (cnt[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return res;
    }
    
}

---

References:

• https://en.wikipedia.org/wiki/Topological_sorting#:~:text=In%20computer%20science%2C%20a%20topological,before%20v%20in%20the%20ordering.
• https://leetcode.com/problems/build-a-matrix-with-conditions/
• https://leetcode.com/problems/build-a-matrix-with-conditions/discuss/2492762/C%2B%2B-Python-Java-Topological-Sort

相似题目：

• https://leetcode.com/problems/course-schedule/
• https://leetcode.com/problems/course-schedule-ii/