Leet Code Daily 2024-07-21 - Build a Matrix with Conditions

class Solution {
public:
    pair<bool, shared_ptr<vector<int>>> tsort(int k,
                                              vector<vector<int>>& conditions) {
        auto ret = make_shared<vector<int>>(k, 0);
        auto next = vector<vector<int>>(k, vector<int>());
        auto count = vector<int>(k, 0);
        for (const auto& condition : conditions) {
            next[condition[0] - 1].push_back(condition[1] - 1);
            count[condition[1] - 1]++;
        }
        queue<int> queue;
        for (int i = 0; i < k; i++) {
            if (count[i] == 0) {
                queue.push(i);
            }
        }
        int next_pos = 0;
        for (; !queue.empty(); queue.pop()) {
            int u = queue.front();
            for (const auto& v : next[u]) {
                if (--count[v] == 0) {
                    queue.push(v);
                }
            }
            (*ret)[u] = next_pos++;
        }
        return make_pair(next_pos == k, ret);
    }

    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions,
                                    vector<vector<int>>& colConditions) {

        auto [ok_row, row_pos] = tsort(k, rowConditions);
        auto [ok_col, col_pos] = tsort(k, colConditions);

        if (!ok_row || !ok_col) {
            return vector<vector<int>>();
        }

        auto ret = vector<vector<int>>(k, vector<int>(k, 0));
        for (int i = 0; i < k; i++) {
            ret[(*row_pos)[i]][(*col_pos)[i]] = i + 1;
        }
        return ret;
    }
};