Beats 99% | Easy Topological Sort | Cycle Detection | Simple Approach
IntuitionThe problem requires constructing a 𝑘 × 𝑘 matrix such that two independent sets of conditions on rows and columns are satisfied. The key insight is tha
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires constructing a `𝑘 × 𝑘` matrix such that two independent sets of conditions on rows and columns are satisfied. The key insight is that the problem can be approached as two topological sorting tasks:

1. One for row constraints.
2. Another for column constraints.

The matrix construction is guided by these two topological orders.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Model the Problem as a Directed Graph:

    - Treat each element from 1 to k as a node.
    - Use the `rowConditions` and `colConditions` to create two directed graphs:
        - One for row constraints (`adjRow`).
        - One for column constraints (`adjCol`).
2. Topological Sorting:

    - Use DFS-based topological sorting to find the order of elements in rows and columns.
    - If a cycle is detected during topological sorting, return an empty matrix (`{}`), as the constraints cannot be satisfied.
3. Construct the Matrix:

    - Map the topological orders into indices for rows and columns.
    - Place the numbers in the matrix at their respective positions where the row index matches the topological order for rows and the column index matches the topological order for columns.
4. Edge Cases:

    - If the constraints result in cycles, return `{}`.
Ensure all numbers from 1 to k are included in the topological sort.    
    - If any are missing, return `{}`.

# Complexity
- Time complexity:
    - *Building the Graphs*: $$O(n+m)$$, where n is the size of `rowConditions` and m is the size of `colConditions`.
    - *Topological Sorting*: $$O(k+E)$$, where E is the number of edges in the graph (proportional to n+m).
    - *Constructing the Matrix*: $$O(k^2)$$, as we iterate over a k×k matrix.
    - **Total**: $$O(n+m+k^2)$$.
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(k + n + m)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    bool topoSort(stack<int> &s, vector<int> &vis, int node, vector<vector<int>> &adj,
    vector<int> &dfsVis){
        vis[node] = 1;
        dfsVis[node] = 1;
        for(auto neighbour : adj[node]){
            if(!vis[neighbour]){
                bool cycle = topoSort(s, vis, neighbour, adj, dfsVis);
                if(cycle) return true;
            }else if(dfsVis[neighbour]){
                return true;
            }
        }

        s.push(node);
        dfsVis[node] = 0;

        return false;
    }
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
        int n = rowConditions.size();
        int m = colConditions.size();
        vector<vector<int>> adjRow(k+1);
        vector<vector<int>> adjCol(k+1);

        for(int i = 0; i < n; i++){
            adjRow[rowConditions[i][0]].push_back(rowConditions[i][1]);
        }

        for(int i = 0; i < m; i++){
            adjCol[colConditions[i][0]].push_back(colConditions[i][1]);
        }

        stack<int> row, col;
        vector<int> visRow(k+1, 0), visCol(k+1, 0);
        vector<int> dfsVisRow(k+1, 0), dfsVisCol(k+1, 0);
        for(int i = 1; i <= k; i++){
            if(!visRow[i]){
                bool cycle = topoSort(row, visRow, i, adjRow, dfsVisRow);
                if(cycle) return {};
            }
        }

        for(int i = 1; i <= k; i++){
            if(!visCol[i]){
                bool cycle = topoSort(col, visCol, i, adjCol, dfsVisCol);
                if(cycle) return {};
            }
        }

        vector<int> ansRow, ansCol;

        while(!row.empty()){
            ansRow.push_back(row.top());
            row.pop();
        }

        while(!col.empty()){
            ansCol.push_back(col.top());
            col.pop();
        }

        /* if(ansRow.size() != k || ansCol.size() != k){
            return {};
        } */

        vector<vector<int>> matrix(k, vector<int> (k, 0));
        for(int i = 0; i < k; i++){
            for(int j = 0; j < k; j++){
                if(ansRow[i] == ansCol[j]){
                    matrix[i][j] = ansRow[i];
                }
            }
        }

        return matrix;
    }
};
```
['Array', 'Graph', 'Topological Sort', 'Matrix', 'C++']