C++ || independent topological sort
Topological sort for rows and cols independently and then combine the outcome.\n\n\n    static vector<vector<int>> buildMatrix(int k,\n\t        vector<vector<i
Topological sort for rows and cols independently and then combine the outcome.\n\n```\n    static vector<vector<int>> buildMatrix(int k,\n\t        vector<vector<int>>& rowConditions,\n\t\t    vector<vector<int>>& colConditions) {\n        // Topological sort for rows and cols independently.\n        const vector<int> row_order = tsort(k, rowConditions);\n        if (empty(row_order)) return {};\n        \n        const vector<int> col_order = tsort(k, colConditions);\n        if (empty(col_order)) return {};\n        \n        // Turnt the tsort into an index so we know in which column a\n        // number should go.\n        vector<int> col_index(k);\n        for (int i = 0; i < size(col_order); ++i) {\n            col_index[col_order[i] - 1] = i;\n        }\n\n        // Build the answer based on the above.\n        vector<vector<int>> ans(k, vector<int>(k));\n        for (int i = 0; i < size(row_order); ++i) {\n            int n = row_order[i];\n            ans[i][col_index[n - 1]] = n;\n        }\n        \n        return ans;\n    }\n```\t\n\nFor topological sort we use the classic Kahn\'s algorithm:\n\n```\n    // Kahn\'s algorithm for topological sort.\n    static vector<int> tsort(int k, const vector<vector<int>>& conds) {\n        // Build adjacency list and in-degree vector.\n        vector<vector<int>> adj(k + 1);\n        vector<int> in_deg(k + 1);\n        for (const vector<int>& cond : conds) {\n            const int before = cond[0];\n            const int after = cond[1];\n            adj[before].push_back(after);\n            ++in_deg[after];\n        }\n        \n        // Topological sort.\n        queue<int> q;\n        for (int i = 1; i <= k; ++i) {\n            if (!in_deg[i]) q.push(i);\n        }\n        \n        vector<int> ans;\n        ans.reserve(k);\n        while (!empty(q)) {\n            const int node = q.front(); q.pop();\n            ans.push_back(node);\n            for (int next : adj[node]) {\n                if (!--in_deg[next]) {\n                    q.push(next);\n                }\n            }\n        }\n        \n        if (size(ans) != k) return {};\n\n        return ans;\n    }\n```
['Topological Sort', 'C']