C++ | Topological sort | 100% Faster, 0ms | Easy Code to follow
Please Upvote :)\n\n\nclass Solution {\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditio
Please Upvote :)\n\n```\nclass Solution {\npublic:\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        vector<vector<int>> v(k,vector<int>(k,0));\n        auto p=topo(rowConditions,k);\n        auto q=topo(colConditions,k);\n        if(p.size()==0 || q.size()==0)// if any of both have cycle\n            return {};\n        for(int i=1;i<p.size();i++)\n        {\n            // p[i] gives row topological index for i and q[i] gives column topological index for i\n            v[p[i]][q[i]]=i;\n        }\n        return v;\n    }\n    vector<int> topo(vector<vector<int>>& v,int k)\n    {\n        vector<vector<int>> adj(k+1);\n        for(auto x:v)\n        {\n            adj[x[0]].push_back(x[1]);\n        }\n        \n        stack<int> s;\n        vector<int> vis(k+1,0);\n        for(int i=1;i<=k;i++)\n        {\n            if(vis[i]==0)\n                dfs(adj,vis,s,i);\n        }\n        vector<int> res(k+1);\n        int ind=0;\n        while(!s.empty())\n        {\n            res[s.top()]=ind;\n            s.pop();\n            ind++;\n        }\n        // check if cycle is there or not\n        for(int i=1;i<=k;i++)\n        {\n            for(auto x:adj[i])\n            {\n                if(res[i]>res[x])// cycle exist\n                    return {};\n            }\n        }\n        return res;\n    }\n    void dfs(vector<vector<int>>& adj,vector<int>& vis,stack<int>& s,int i)\n    {\n        vis[i]=1;\n        for(auto x:adj[i])\n        {\n            if(vis[x]==0)\n                dfs(adj,vis,s,x);\n        }\n        s.push(i);// recursively put the parent in top of the child\n    }\n};\n```
['Depth-First Search', 'Graph', 'Topological Sort', 'C', 'C++']