C++ / Python Solution | Matrix | Graph | Topological Sorting | Kahn's Algorithm |
Intuition\nTopological Sorting.\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nUse Kahn\'s Algorithm.\n Describe your approach to 
# Intuition\nTopological Sorting.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nUse Kahn\'s Algorithm.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(K^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(K^2)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n\n    bool toposort(vector<vector<int>> &adj, vector<int> &tsort, vector<int> &ind)\n    {\n        int V = ind.size();\n        queue<int> q;\n        \n        for(int i=0 ; i<V ; i++) if(ind[i] == 0) q.push(i);\n\n        while(!q.empty())\n        {\n            int u = q.front();\n            q.pop();\n            tsort.push_back(u);\n\n            for(auto &v: adj[u])\n            {\n                ind[v] -= 1;\n                if(ind[v] == 0) q.push(v);\n            }\n        }\n\n        if(tsort.size() != V) return false;\n        return true;\n    }\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        \n        vector<vector<int>> adj_row(k, vector<int> ());\n        vector<vector<int>> adj_col(k, vector<int> ());\n\n        vector<int> ind_row(k, 0);\n        vector<int> ind_col(k, 0);\n\n        for(auto &edge: rowConditions) \n        {\n            adj_row[edge[0]-1].push_back(edge[1]-1);\n            ind_row[edge[1]-1] += 1;\n        }\n\n        for(auto &edge: colConditions) \n        {\n            adj_col[edge[0]-1].push_back(edge[1]-1);\n            ind_col[edge[1]-1] += 1;\n        }\n        \n        vector<int> tsort_row;\n        vector<int> tsort_col;\n\n        bool notCycle_row = toposort(adj_row, tsort_row, ind_row);\n        bool notCycle_col = toposort(adj_col, tsort_col, ind_col);\n\n        if(!notCycle_row || !notCycle_col) return {};\n        vector<vector<int>> ans(k, vector<int> (k, 0));\n\n        for(int row = 0 ; row < k ; row++)\n        {\n            int col = find(tsort_col.begin(), tsort_col.end(), tsort_row[row]) - tsort_col.begin();\n            ans[row][col] = tsort_row[row]+1;\n        }\n\n        return ans;\n    }\n};\n```\n\n```Python []\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n        \n        def toposort(adj, tsort, ind):\n            V = len(ind)\n            q = deque()\n            for i in range(V):\n                if ind[i] == 0:\n                    q.append(i)\n\n            while q:\n                u = q.popleft()\n                tsort.append(u)\n                for v in adj[u]:\n                    ind[v] -= 1\n                    if ind[v] == 0:\n                        q.append(v)\n\n            if len(tsort) != V: \n                return False\n            return True\n        # End\n\n        adj_row = [[] for i in range(k)]\n        adj_col = [[] for i in range(k)]\n\n        ind_row = [0] * k\n        ind_col = [0] * k\n\n        for edge in rowConditions: \n            adj_row[edge[0]-1].append(edge[1]-1)\n            ind_row[edge[1]-1] += 1\n\n        for edge in colConditions: \n            adj_col[edge[0]-1].append(edge[1]-1)\n            ind_col[edge[1]-1] += 1\n        \n        tsort_row, tsort_col = [], []\n\n        notCycle_row = toposort(adj_row, tsort_row, ind_row)\n        notCycle_col = toposort(adj_col, tsort_col, ind_col)\n\n        if not notCycle_row or not notCycle_col:\n            return []\n        \n        ans = [[0] * k for i in range(k)]\n        for row in range(k):\n            col = tsort_col.index(tsort_row[row])\n            ans[row][col] = tsort_row[row]+1\n\n        return ans\n```
['Array', 'Graph', 'Topological Sort', 'Matrix', 'C++', 'Python3']