C++ | Topological Sort
Perform topological sort on rowConditions & colConditions\n The index of element in topological sort of rowConditions will be the rowIndex. Similarly, for the i
* Perform **topological sort** on rowConditions & colConditions\n* The index of element in topological sort of rowConditions will be the rowIndex. Similarly, for the index of element in topological sort of colConditions will the colIndex of the element in the result grid\n* Time complexity of Topological sort is ```O(V + E)```, where V = No. of vertices = k and E = No. of Edges which can be atmost ```k * (k - 1) / 2```  \n* So, Time complexity: ```O(k ^ 2)``` | Space complexity: ```O(k ^ 2)```\n(Initialising the 2D vector also takes ```k ^ 2``` time complexity)\n\n![image](https://assets.leetcode.com/users/images/df9b108f-3f00-4484-b7f7-8e2ff758dfb2_1661658583.621787.png)\n\n```\nclass Solution {\npublic:\n    // Same Code as Course Schedule - 2 \n    vector<int> findOrder(int k, vector<vector<int>>& dependencies) {\n                \n        vector<vector<int>> adj(k + 1);\n        vector<int> indegree(k + 1);\n        for(auto dependency: dependencies) {\n            adj[dependency[0]].push_back(dependency[1]);\n            indegree[dependency[1]]++;\n        }\n        \n        queue<int> q;\n        for(int i = 1; i <= k; i++) {\n            if(indegree[i] == 0) {\n                q.push(i);\n            }\n        }\n        \n        int cnt = 0;\n        vector<int> order;\n        while(!q.empty()) {\n            \n            int cur = q.front();\n            q.pop();\n            \n            cnt++;\n            order.push_back(cur);\n            \n            for(int nbr: adj[cur]) {\n                indegree[nbr]--;\n                \n                if(indegree[nbr] == 0) {\n                    q.push(nbr);\n                }\n            }\n        }\n        \n        if(cnt == k) return order;\n        return {};\n    }\n    \n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        vector<int> rowArray = findOrder(k, rowConditions);  \n        vector<int> colArray = findOrder(k, colConditions);\n        \n        // If one of the row conditions or col conditions has a cycle\n        if(rowArray.size() == 0 || colArray.size() == 0) {\n            return {};\n        }\n        \n        vector<pair<int, int>> ind(k);   // list of indices (i, j) for k values\n\t\t// from topological ordering deriving the indices for the values\n        for(int i = 0; i < k; i++) {\n            ind[rowArray[i] - 1].first = i;  \n            ind[colArray[i] - 1].second = i;\n        }\n        \n        vector<vector<int>> result(k, vector<int>(k, 0));\n\t\t// iterate over the values and place then in the result grid\n        for(int i = 0; i < k; i++) {\n            result[ind[i].first][ind[i].second] = i + 1;\n        }\n        return result;\n    }\n};\n```\n
['Topological Sort', 'C']