2392 - Build a Matrix With Conditions

 JAVA

class Solution {
    List<Integer>[] al;
    
    public int[][] buildMatrix(int k, int[][] rc, int[][] cc) {
        
        int ans[][] = new int[k][k];
        this.al = new ArrayList[k+1];
        
        for(int i=0;i<=k;i++) al[i] = new ArrayList<>();
        for(int r[] : rc) al[r[0]].add(r[1]);
        
        boolean[] vis = new boolean[k+1];
        boolean dfsvis[] = new boolean[k+1];
        List<Integer> rowStack = new ArrayList<>();
        
        for(int node=1;node<=k;node++){
            if(!vis[node]) {
                if(!dfs(node,vis,rowStack,dfsvis)) return new int[0][0];
            }
        }

        for(int i=0;i<=k;i++) al[i] = new ArrayList<>();
        for(int c[] : cc) al[c[0]].add(c[1]);
        List<Integer> colStack = new ArrayList<>();
        
        vis = new boolean[k+1];
        dfsvis = new boolean[k+1];
        
        for(int node=1;node<=k;node++){
            if(!vis[node]) {
                if(!dfs(node,vis,colStack,dfsvis)) return new int[0][0];
            }
        }
        
        HashMap<Integer,Integer> map = new HashMap<>();
        
        for(int i=0;i<colStack.size();i++){
            map.put(colStack.get(i),i);
        }
        
        int row = 0;
        
        for(int i=rowStack.size()-1;i>=0;i--){
			ans[row++][k-map.get(rowStack.get(i))-1] = rowStack.get(i);
        }
        
        return ans;
    
    }
    
	private boolean dfs(int node,boolean[] vis,List<Integer> stack,boolean[] dfsvis){
        vis[node] = true;
        dfsvis[node] = true;
        for(int next : al[node]){
            if(!vis[next]) {
                if(!dfs(next,vis,stack,dfsvis)) return false;
            }else if(dfsvis[next]) return false;
        }
        stack.add(node);
        dfsvis[node] = false;
        return true;
    }
}

C++

• class Solution {
  public:
      int k;
  
      vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
          this->k = k;
          auto row = f(rowConditions);
          auto col = f(colConditions);
          if (row.empty() || col.empty()) return {};
          vector<vector<int>> ans(k, vector<int>(k));
          vector<int> m(k + 1);
          for (int i = 0; i < k; ++i) {
              m[col[i]] = i;
          }
          for (int i = 0; i < k; ++i) {
              ans[i][m[row[i]]] = row[i];
          }
          return ans;
      }
  
      vector<int> f(vector<vector<int>>& cond) {
          vector<vector<int>> g(k + 1);
          vector<int> indeg(k + 1);
          for (auto& e : cond) {
              int a = e[0], b = e[1];
              g[a].push_back(b);
              ++indeg[b];
          }
          queue<int> q;
          for (int i = 1; i < k + 1; ++i) {
              if (!indeg[i]) {
                  q.push(i);
              }
          }
          vector<int> res;
          while (!q.empty()) {
              for (int n = q.size(); n; --n) {
                  int i = q.front();
                  res.push_back(i);
                  q.pop();
                  for (int j : g[i]) {
                      if (--indeg[j] == 0) {
                          q.push(j);
                      }
                  }
              }
          }
          return res.size() == k ? res : vector<int>();
      }
  };