# 2392. Build a Matrix With Conditions
###### tags: `Leetcode` `Hard` `BFS` `Topological Sort`
Link: https://leetcode.com/problems/build-a-matrix-with-conditions/
## 思路
topological sort先分配每个数字所在的row number
再topological sort分配每个数字所有的col number
## Code

class Solution {
    public int[][] buildMatrix(int k, int[][] rowConditions, int[][] colConditions) {
        int[][] ans = new int[k][k];
        
        int[] aboveNum = new int[k];
        int[] leftNum = new int[k];
        List<List<Integer>> rowGraph = new ArrayList<>();
        List<List<Integer>> colGraph = new ArrayList<>();
        
        for(int i=0; i<k; i++) rowGraph.add(new ArrayList<>());
        for(int i=0; i<k; i++) colGraph.add(new ArrayList<>());
        for(int[] rowc:rowConditions){
            rowGraph.get(rowc[0]-1).add(rowc[1]-1);
            aboveNum[rowc[1]-1]++;
        }
        for(int[] colc:colConditions){
            colGraph.get(colc[0]-1).add(colc[1]-1);
            leftNum[colc[1]-1]++;
        }
        Map<Integer, Integer> numRow = new HashMap<>();
        Queue<Integer> q = new LinkedList<>();
        for(int i=0; i<aboveNum.length; i++){
            if(aboveNum[i]==0){
                q.add(i);
            }
        }
        
        int idx = 0;
        while(!q.isEmpty()){
            int curr = q.poll();
            numRow.put(curr+1, idx++);
            for(int next:rowGraph.get(curr)){
                aboveNum[next]--;
                if(aboveNum[next]==0){
                    q.add(next);
                }
            }
        }
        q.clear();
        
        if(numRow.size()!=k) return new int[0][0];
        
        for(int i=0; i<leftNum.length; i++){
            if(leftNum[i]==0) q.add(i);
        }
        idx = 0;
        while(!q.isEmpty()){
            int curr = q.poll();
            int row = numRow.get(curr+1);
            ans[row][idx++] = curr+1;
            for(int next:colGraph.get(curr)){
                leftNum[next]--;
                if(leftNum[next]==0){
                    q.add(next);
                }
            }
        }
        if(!q.isEmpty()||idx!=k) return new int[0][0];
        return ans;
    }
}