Build a Matrix With Conditions

class Solution {
private:
    vector<int> topologicalSort(int k, vector<vector<int>>& conditions) {
        vector<vector<int>> graph(k + 1);
        vector<int> inDegree(k + 1, 0);
        vector<bool> seen(k + 1, false);
        
        for (const auto& condition : conditions) {
            graph[condition[0]].push_back(condition[1]);
            inDegree[condition[1]]++;
            seen[condition[0]] = seen[condition[1]] = true;
        }
        
        queue<int> q;
        vector<int> order;
        
        for (int i = 1; i <= k; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
                if (!seen[i]) order.push_back(i);
            }
        }
        
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            if (seen[node]) order.push_back(node);
            
            for (int neighbor : graph[node]) {
                if (--inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        for (int i = 1; i <= k; i++) {
            if (inDegree[i] > 0) return {};
        }
        
        while (order.size() < k) {
            for (int i = 1; i <= k; i++) {
                if (find(order.begin(), order.end(), i) == order.end()) {
                    order.push_back(i);
                    break;
                }
            }
        }
        
        return order;
    }

public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        vector<int> rowOrder = topologicalSort(k, rowConditions);
        vector<int> colOrder = topologicalSort(k, colConditions);
        
        if (rowOrder.empty() || colOrder.empty()) {
            return {};
        }
        
        vector<vector<int>> result(k, vector<int>(k, 0));
        vector<int> rowPosition(k + 1), colPosition(k + 1);
        
        for (int i = 0; i < k; i++) {
            rowPosition[rowOrder[i]] = i;
            colPosition[colOrder[i]] = i;
        }
        
        for (int num = 1; num <= k; num++) {
            result[rowPosition[num]][colPosition[num]] = num;
        }
        
        return result;
    }
};