2392. Build a Matrix With Conditions

You are given a positive integer k. You are also given:

• a 2D integer array rowConditions of size n where rowConditions[i] = [abovei, belowi], and
• a 2D integer array colConditions of size m where colConditions[i] = [lefti, righti].

The two arrays contain integers from 1 to k.

You have to build a k x k matrix that contains each of the numbers from 1 to k exactly once. The remaining cells should have the value 0.

The matrix should also satisfy the following conditions:

• The number abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1.
• The number lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 1.

Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix.

class Solution {
    int vis1[444] = {}, vis2[444];
    int rep[444] = {};
    void dfs1(int u, vector<vector<int>>& adj, vector<int>& st) {
        vis1[u] = true;
        for(auto& v : adj[u]) {
            if(!vis1[v])
                dfs1(v, adj, st);
        }
        st.push_back(u);
    }
    void dfs2(int u, int root, vector<vector<int>>& radj) {
        vis2[u] = true;
        rep[u] = root;
        for(auto& v : radj[u]) {
            if(!vis2[v])
                dfs2(v,root, radj);
        }
    }
    bool check(vector<vector<int>>& E, int k) {
        vector<vector<int>> adj(444);
        vector<vector<int>> radj(444);
        vector<int> st;
        memset(vis1, 0, sizeof vis1);
        memset(vis2, 0, sizeof vis2);
        memset(rep, 0, sizeof rep);
        for(auto& e : E) {
            int u = e[0], v = e[1];
            adj[u].push_back(v);
            radj[v].push_back(u);
        }
        for(int i = 1; i <= k; i++) {
            if(!vis1[i]) dfs1(i,adj,st);
        }
        while(!st.empty()) {
            auto u = st.back(); st.pop_back();
            if(vis2[u]) continue;
            dfs2(u,u,radj);
        }
        for(int i = 1; i <= k; i++) {
            if(!rep[i]) continue;
            if(rep[i] != i) return false;
        }
        return true;
    }
    vector<int> indgree(vector<vector<int>>& E, int k) {
        vector<int> res(444);
        vector<vector<int>> adj(444);
        vector<int> ind(444);
        for(auto& e : E) {
            int u = e[0], v = e[1];
            adj[u].push_back(v);
            ind[v] += 1;
        }
        queue<int> q;
        for(int i = 1; i <= k; i++) {
            if(ind[i] == 0) q.push(i);
        }
        int now = 1;
        while(!q.empty()) {
            auto u = q.front(); q.pop();
            res[u] = now++;
            for(auto& v : adj[u]) {
                if(--ind[v] == 0) q.push(v);
            }
        }

        return res;
    }
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<vector<int>> res(k, vector<int>(k));
        if(!check(rowConditions, k) or !check(colConditions, k)) return {};
        vector<int> row = indgree(rowConditions, k), col = indgree(colConditions, k);
        vector<int> any,rowAny,colAny;
        for(int i = 1; i <= k; i++) {
            int r = row[i], c = col[i];
            if(r and c) res[r-1][c-1] = i;
            else if(!r and !c) any.push_back(i);
            else if(r and !c) rowAny.push_back(i);
            else if(!r and c) colAny.push_back(i);
        }
        for(auto& n : rowAny) {
            int r = row[n];
            for(int i = 0; i < k; i++) {
                if(res[r][i]) continue;
                res[r][i] = n;
                break;
            }
        }
        for(auto& n : colAny) {
            int c = col[n];
            for(int i = 0; i < k; i++) {
                if(res[i][c]) continue;
                res[c][i] = n;
                break;
            }
        }
        int p = 0;
        for(int i = 0; i < k and p < any.size(); i++) {
            for(int j = 0; j < k and p < any.size(); j++) {
                if(res[i][j]) continue;
                res[i][j] = any[p++];
            }
        }
        return res;
    }
};