Easy to Understand
Intuition\n Describe your first thoughts on how to solve this problem. \nTopological Ordering.\n# Approach\n Describe your approach to solving the problem. \nTh
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTopological Ordering.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe problem is composition of two medium problem\n1.detecting cycle for edges case\n2.Degree vector is used to assign the topological ordering to elements.\n3.First I will check for node which have 0 indegree and place it in topologically(queue) available left end and then decrease the degree of all adjacent elements.\n4.Now again check which element is having currently zero indegree.\n5.put all those to the queue again. \n\nThe above steps(3,4,5) will continue until all the element has 0 indegree.\n\nDo this for row and coloumn seperately.\n\nrow vector is saying that particular element 1<=i<=k(1 based indexing)belongs to row[i] row in k*k matrix;\nsimilar for col.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(2*(n+k) + 2*(n+k) + k*k)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO((n+k) + (k))\n# Code\n```\n#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)\n#define ull unsigned long long int\n#define yes cout << "YES" << endl\n#define no cout << "NO" << endl\n#define ll long long int\n#define mii unordered_map<int,int>\n#define loop(i,s, e) for (int i = s; i < e; i++)\n#define show(x) cout<<x<<" ";\n#define pii pair<int,int>\n#define vi vector<int>\n#define pb push_back\n#define rr return\n#define s second\n#define f first\n#define inf 1e9\nconst int mod = 1e9+7;\nconst int N = 2e5+5;\n\nclass Solution {\n    bool dfs(vector<int> adj[] , vector<int>& vis , vector<int>& pathvis ,int n){\n        vis[n]=1;\n        pathvis[n]=1;\n        for(auto it:adj[n])\n        if(!vis[it]){\n            if(dfs(adj , vis , pathvis , it)== true){\n                return true;\n            }\n        }\n        else if (pathvis[it]){\n            return true;\n        }  \n        pathvis[n]=0;\n        return false;\n    }\nbool cycle(int V, vector<int> adj[]) {\n        vector<int> vis(V+1,0);\n        vector<int> pathvis(V+1,0);\n        \n        for(int i = 1 ; i<=V ; i ++){\n            if(!vis[i]){\n                if(dfs(adj , vis , pathvis , i)==true){\n                    return true;\n                }\n            }\n        }\n        return false;\n    }\nvector<int> decide(vector<int> adj[],vector<int>& degree, int k){\n    queue<int> q;\n    vector<int> ans(k+1);\n    loop(i,1,k+1){\n        if (degree[i]==0)q.push(i);\n    }\n    int tt = 0;\n    while(!q.empty()){\n        int id = q.front();\n        q.pop();\n        ans[id]=tt++;\n        for (auto x:adj[id]){\n            degree[x]--;\n            if (degree[x]==0)q.push(x);\n        }\n    }\n    return ans;\n}\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        vector<int> adj[k+1];\n        vector<int> degree(k+1);\n        for (auto x:rowConditions){\n            adj[x[0]].pb(x[1]);\n            degree[x[1]]++;\n        }\n        if (cycle(k,adj)){return {};}\n        vector<int> row = decide(adj,degree,k);\n        loop(i,1,k+1){\n            adj[i].clear();\n            degree[i]=0;\n        }\n        for (auto x:colConditions){\n            adj[x[0]].pb(x[1]);\n            degree[x[1]]++;\n        }\n        if (cycle(k,adj)){return {};}\n        vector<int> col= decide(adj,degree,k);\n        vector<vector<int>> ans(k,vector<int>(k));\n        loop(i,1,k+1){\n            ans[row[i]][col[i]] = i;\n        }\n        return ans;\n    }\n};\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Graph', 'Topological Sort', 'C++']