Topological Sort
We apply topological sort independently for both conditions. \n\nAs a refresher, we build a directed graph with k nodes, and each condition is a directed link b
We apply topological sort independently for both conditions. \n\nAs a refresher, we build a directed graph with `k` nodes, and each condition is a directed link between the corresponding nodes.\n\n> We represent the graph with the adjacency list (`al`). Note that we use a set to hold linked nodes as we may have duplicated conditions in the input.\n\nWe also track the number of conditions for each note in the `pre` array.\n\nTo get the sorted sequence, we do BFS starting from nodes with zero conditions.\n\nFor each node in the BFS queue `q`, we add it to the sequence, and then decrease the number of conditions for all connected notes. If the number of conditions for some node becomes zero, we add it to the BFS queue.\n\nIf there is a cycle, the topological sort would not produce all `k` elements.\n\nAfter we have an order of elements, we use it to sort indexes [0..k-1] to figure out where each element goes into the matrix.\n\n**C++**\n```cpp\nvector<int> top_sort(int k, vector<vector<int>>& conditions) {\n    vector<int> sorted, id(k), pre(k + 1), q;\n    vector<unordered_set<int>> al(k + 1);\n    for (auto &c : conditions)\n        if(al[c[0]].insert(c[1]).second)\n            ++pre[c[1]];\n    for (auto i = 1; i <= k; ++i)\n        if (pre[i] == 0)\n            q.push_back(i);\n    while (!q.empty()) {\n        vector<int> q1;\n        for (auto i : q) {\n            sorted.push_back(i);\n            for (auto j : al[i])\n                if (--pre[j] == 0)\n                    q1.push_back(j);\n        }\n        swap(q, q1);\n    }\n    if (sorted.size() != k)\n        return {};\n    iota(begin(id), end(id), 0);\n    sort(begin(id), end(id), [&](int a, int b){ return sorted[a] < sorted[b]; });    \n    return id;\n}\nvector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n    auto rid = top_sort(k, rowConditions), cid = top_sort(k, colConditions);\n    if (rid.empty() || cid.empty())\n        return {};\n    vector<vector<int>> res(k, vector<int>(k));    \n    for (int i = 1; i <= k; ++i)\n        res[rid[i - 1]][cid[i - 1]] = i;\n    return res;\n}\n```
[]