#2392 Build a Matrix With Conditions

1class Solution {2    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {3        int[] rowPos = positions(k, rowConditions);4        int[] colPos = positions(k, colConditions);5        if (rowPos == null || colPos == null) return new int[0][0];6        int[][] matrix = new int[k][k];7        for (int v = 1; v <= k; v++) matrix[rowPos[v]][colPos[v]] = v;8        return matrix;9    }10 11    /** pos[v] = index of v in a topological order (reverse post-order), or null on a cycle. */12    private int[] positions(int k, int[][] conditions) {13        List<List<Integer>> adj = new ArrayList<>();14        for (int i = 0; i <= k; i++) adj.add(new ArrayList<>());15        for (int[] c : conditions) adj.get(c[0]).add(c[1]);16        int[] color = new int[k + 1];17        List<Integer> post = new ArrayList<>();18        for (int v = 1; v <= k; v++) if (color[v] == 0 && !dfs(v, adj, color, post)) return null;19        int[] pos = new int[k + 1];20        for (int i = 0; i < k; i++) pos[post.get(i)] = k - 1 - i; // reversed post-order21        return pos;22    }23 24    private boolean dfs(int u, List<List<Integer>> adj, int[] color, List<Integer> post) {25        color[u] = 1;26        for (int v : adj.get(u)) {27            if (color[v] == 1) return false;28            if (color[v] == 0 && !dfs(v, adj, color, post)) return false;29        }30        color[u] = 2;31        post.add(u);32        return true;33    }34}

1class Solution {2    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {3        int[] rowOrder = topo(k, rowConditions);4        int[] colOrder = topo(k, colConditions);5        if (rowOrder.length == 0 || colOrder.length == 0) return new int[0][0]; // a cycle somewhere6        int[] rowOf = new int[k + 1], colOf = new int[k + 1];7        for (int i = 0; i < k; i++) {8            rowOf[rowOrder[i]] = i;9            colOf[colOrder[i]] = i;10        }11        int[][] matrix = new int[k][k];12        for (int v = 1; v <= k; v++) matrix[rowOf[v]][colOf[v]] = v; // rows and columns are independent13        return matrix;14    }15 16    /** Kahn on values 1..k; edge {above, below} or {left, right}. Returns [] on a cycle. */17    private int[] topo(int k, int[][] conditions) {18        List<List<Integer>> adj = new ArrayList<>();19        for (int i = 0; i <= k; i++) adj.add(new ArrayList<>());20        int[] indegree = new int[k + 1];21        for (int[] c : conditions) {22            adj.get(c[0]).add(c[1]);23            indegree[c[1]]++;24        }25        Deque<Integer> queue = new ArrayDeque<>();26        for (int v = 1; v <= k; v++) if (indegree[v] == 0) queue.offer(v);27        int[] order = new int[k];28        int idx = 0;29        while (!queue.isEmpty()) {30            int u = queue.poll();31            order[idx++] = u;32            for (int v : adj.get(u)) if (--indegree[v] == 0) queue.offer(v);33        }34        return idx == k ? order : new int[0];35    }36}