C++ Basic Topological Sort Approach
Intuition\n Describe your first thoughts on how to solve this problem. \nIn this problem we are given \'k\' number of elements that is 1 through k\nalong with t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIn this problem we are given \'k\' number of elements that is 1 through k\nalong with the relative order between some of the elements\nthe order is given in two formats that is row-wise and column-wise which we need to maintain in the resultant matrix\nIf we assume these k elements to be a part of two graphs:-\nrowAdj & colAdj where rowConditions contains the directed edges {u, v} such that there is an edge from u to v for the graph rowAdj and colConditions contains the same for colAdj\nThen this problem can be seen as a topological sorting problem\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst we create the graphs rowAdj and colAdj based on rowConditions and colConditions respectivly\nAfter that we check for cycles in both the graphs\nIf there exists any cycle in any of the newly obtained graphs, we will return an empty 2D matrix because topoSort is not possible in that case\nafter we have obtained the topological sort for both the graphs, we record the appropriate positions of these elements in the vector rowOrder for rowAdj and colOrder for colAdj\nNow that we have the positions for these elements in the matrix we can easily construct the matrix.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(rowConditions.length + colConditions.length + k)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(k * k)$$\n\n# Code\n```\nclass Compare {\npublic:\n    bool operator()(vector<int> below, vector<int> above) {\n        return above[0] > below[0];\n    }\n};\n\nclass Solution {\n\n    bool isCyclic(vector<int>* adj, int cur, vector<bool>& dfsvis, vector<bool>& vis) {\n        if(dfsvis[cur]) {\n            return true;\n        }\n\n        if(vis[cur]) {\n            return false;\n        }\n        vis[cur] = true;\n\n        bool cyclic = false;\n        dfsvis[cur] = true;\n        for(int x: adj[cur]) {\n            cyclic |= isCyclic(adj, x, dfsvis, vis);\n        }\n        dfsvis[cur] = false;\n\n        return cyclic;\n    }\n\n    void topoSort(stack<int>& sortedElements, vector<int>* adj, int curr, vector<bool>& vis) {\n        if(vis[curr]) {\n            return;\n        }\n        vis[curr] = true;\n\n        for(int x: adj[curr]) {\n            topoSort(sortedElements, adj, x, vis);\n        }\n        sortedElements.push(curr + 1);\n    }\n\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        \n        vector<vector<int>> temp;\n\n\n        vector<int> rowAdj[k];\n        vector<int> rowOutDegree(k, 0);\n        priority_queue<vector<int>, vector<vector<int>>, Compare> rowPQ;\n        vector<bool> row1Vis(k, false);\n        vector<bool> row1DfsVis(k, false);\n        for(auto x: rowConditions) {\n            rowAdj[x[0] - 1].push_back(x[1] - 1);\n            rowOutDegree[x[0] - 1]++;\n            rowOutDegree[x[1] - 1]--;\n        }\n\n        for(int i = 0; i < k; i++) {\n            if(isCyclic(rowAdj, i, row1DfsVis, row1Vis)) {\n                return temp;\n            }\n        }\n\n        for(int i = 0; i < k; i++) {\n            rowPQ.push({rowOutDegree[i], i});\n        }\n\n        vector<int> colAdj[k];\n        vector<int> colOutDegree(k, 0);\n        priority_queue<vector<int>, vector<vector<int>>, Compare> colPQ;\n        vector<bool> col1Vis(k, false);\n        vector<bool> col1DfsVis(k, false);\n        for(auto x: colConditions) {\n            colAdj[x[0] - 1].push_back(x[1] - 1);\n            colOutDegree[x[0] - 1]++;\n            colOutDegree[x[1] - 1]--;\n        }\n\n        for(int i = 0; i < k; i++) {\n            if(isCyclic(colAdj, i, col1DfsVis, col1Vis)) {\n                return temp;\n            }\n        }\n\n        for(int i = 0; i < k; i++) {\n            colPQ.push({colOutDegree[i], i});\n        }\n\n        stack<int> rowSortedElements;\n        vector<bool> rowVis(k, false);\n        stack<int> colSortedElements;\n        vector<bool> colVis(k, false);\n\n        while(!rowPQ.empty()) {\n            int node1 = rowPQ.top()[1];\n            rowPQ.pop();\n            if(!rowVis[node1]) {\n                topoSort(rowSortedElements, rowAdj, node1, rowVis);\n            }\n            int node2 = colPQ.top()[1];\n            colPQ.pop();\n            if(!colVis[node2]) {\n                topoSort(colSortedElements, colAdj, node2, colVis);\n            }\n        }\n\n        vector<int> rowOrder(k+1);\n        vector<int> colOrder(k+1);\n        while(!rowSortedElements.empty()) {\n            rowOrder[rowSortedElements.top()] = k - rowSortedElements.size();\n            rowSortedElements.pop();\n            colOrder[colSortedElements.top()] = k - colSortedElements.size();\n            colSortedElements.pop();\n        }\n        \n        vector<vector<int>> ans(k, vector<int>(k, 0));\n\n        for(int i = 1; i <= k; i++) {\n            ans[rowOrder[i]][colOrder[i]] = i;\n        }\n\n        return ans;\n    }\n};\n```
['Depth-First Search', 'Graph', 'Topological Sort', 'Matrix', 'C++']