C++ - Quick Explained Code - Topo Sort, Kahn's Algo
Thought Process:\n This is an interesting problem, specially to see how graph helps solve this.\n Reading the problem with the rowConditions and columnCondition
**Thought Process:**\n* This is an interesting problem, specially to see how graph helps solve this.\n* Reading the problem with the `rowConditions` and `columnConditions` does give the hint that applying topological sort would make sense here.\n* So we do the topo sort, and sparsely set the index across columns. Together, we apply it on rows and get one of the possible combinations.\n* **Edge case**: We can check if building matrix is not possible, which is when graph is cyclic i.e.  `topo output size != N`.\n\n```cpp\nvector<int> topoSort(vector<vector<int>> conditions, int k){\n    vector<int> indegree(k+1);\n    unordered_map<int, vector<int>> graph;\n\n    //building graph and indegree\n    for(auto cond: conditions){\n        graph[cond[0]].push_back(cond[1]);\n        indegree[cond[1]]++;\n    }\n\n    //building the topo sort queue (0 degree nodes)\n    queue<int> q;\n    for(int i=1; i <= k; i++){\n        if(indegree[i] == 0)\n            q.push(i);\n    }\n\n    //building the topo ordered output\n    vector<int> res;\n    while(!q.empty()){\n        int node = q.front(); q.pop();\n        res.push_back(node);\n\n        for(int child: graph[node]){\n            indegree[child]--;\n            if(indegree[child] == 0)\n                q.push(child);\n        }\n    }\n    return res;\n}\n\nvector<vector<int>> buildMatrix(int k, vector<vector<int>>& RowConditions, vector<vector<int>>& ColConditions) {\n    vector<int> rows = topoSort(RowConditions, k),\n                cols = topoSort(ColConditions, k);\n\n    // Acc to Kahn\'s algo, if topo output size != N, then it\'s cyclic\n    if(rows.size() != k || cols.size() != k) return {};\n\n    vector<vector<int>> res(k, vector<int>(k, 0));\n    vector<int> colIdx(k+1, 0);\n\n    // The cols array has [most dependent,.. -> ..,least dependent elemts]\n    // For colConditions = [[2,1],[3,2]], it will be [3,2,1]\n    // val 3 -> idx 0\n    // val 2 -> idx 1\n    // val 1 -> idx 2\n    for(int j=0; j < k; j++)\n        colIdx[cols[j]] = j;\n\n    // In each row, place the "row[i]" value at the j th index, \n    // we sparsely allocated just above.\n    for(int i=0; i < k; i++)\n        res[i][colIdx[rows[i]]] = rows[i];\n\n    return res;\n}\n```
['Graph', 'Topological Sort', 'C']