给定条件下构造矩阵

/*
 * Problem: Construct a k x k matrix where each number from 1 to k appears exactly once
 * and the matrix satisfies row and column conditions given by rowConditions and colConditions.
 * Approach:
 * 1. Use topological sorting to determine the order of numbers in rows and columns.
 * 2. If there is a cycle detected during sorting, return an empty matrix.
 * 3. Place the numbers in the matrix according to the determined row and column orders.
 */

import java.util.*;
import java.util.stream.*;

public class MatrixConstructor {
    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        int[][] result = new int[k][k];
        int[] rowOrder = topologicalSort(k, rowConditions);
        int[] colOrder = topologicalSort(k, colConditions);
        if (rowOrder == null || colOrder == null) return new int[0][0];

        Map<Integer, Integer> rowIndex = IntStream.range(0, k)
                .boxed()
                .collect(Collectors.toMap(i -> rowOrder[i], i -> i));
        Map<Integer, Integer> colIndex = IntStream.range(0, k)
                .boxed()
                .collect(Collectors.toMap(i -> colOrder[i], i -> i));

        IntStream.rangeClosed(1, k).forEach(i -> result[rowIndex.get(i)][colIndex.get(i)] = i);

        return result;
    }

    private int[] topologicalSort(int k, int[][] conditions) {
        int[] inDegree = new int[k + 1];
        List<Integer>[] graph = Stream.generate(ArrayList<Integer>::new)
                                      .limit(k + 1)
                                      .toArray(ArrayList[]::new);
        Arrays.stream(conditions).forEach(cond -> {
            graph[cond[0]].add(cond[1]);
            inDegree[cond[1]]++;
        });

        Queue<Integer> queue = IntStream.rangeClosed(1, k)
                                        .filter(i -> inDegree[i] == 0)
                                        .boxed()
                                        .collect(Collectors.toCollection(LinkedList::new));

        int[] order = new int[k];
        int index = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order[index++] = node;
            graph[node].forEach(neighbor -> {
                if (--inDegree[neighbor] == 0) queue.offer(neighbor);
            });
        }

        return index == k ? order : null;
    }
}