Simple and Easy C++ | Kahn's Algorithm | Topological Sort | BFS | OOPS
Algorithm\n1. Create graph for both rowConditions and colConditions.\n2. Check if both graphs are acyclic using Kahn\'s Algorithm. If either graph is cyclic, th
**Algorithm**\n1. Create graph for both ```rowConditions``` and ```colConditions```.\n2. Check if both graphs are acyclic using Kahn\'s Algorithm. If either graph is cyclic, then return ```[]```.\n3. Kahn\'s Algorithm will give ```topological sorting (topo1 and topo2) ``` for both graphs.\n4. ```topo1``` will give position of element according to row.\n5. ```topo2``` will give position of element according to column.\n\n**Code**\n```\nclass graph{\n    int n;\n    vector<vector<int>> adj;\npublic:\n    graph(int n){\n        this->n = n;\n        adj.resize(n);\n    }\n    \n    void add_edge(int u, int v){\n        adj[u].push_back(v);\n    }\n    \n    void make_adj(vector<vector<int>> arr){\n        for(auto& x:arr){\n            this->add_edge(x[0], x[1]);\n        }\n    }\n    \n    vector<int> kahn_algo(){\n        vector<int> indeg(this->n, 0);\n        queue<int> q;\n        vector<int> topo;\n        \n        for(auto &x : this->adj){\n            for(int &y: x){\n                indeg[y]++;\n            } \n        }\n\n        for(int i=1; i<this->n; i++){\n            if(indeg[i] == 0){\n                q.push(i);\n            }\n        }\n\n        while(!q.empty()){\n            int cur = q.front();\n            q.pop();\n\n            topo.push_back(cur);\n            \n            for(auto& x : this->adj[cur]){\n                indeg[x]--;\n                if(indeg[x] == 0){\n                    q.push(x);\n                }\n            }\n        }\n\n        return topo;\n    }\n};\n\nclass Solution {\npublic:\n    vector<vector<int>> solve(int& n, vector<int>& topo1, vector<int>& topo2){\n        if(topo1.size() != n || topo2.size() != n){\n            return {};\n        }\n        \n        vector<vector<int>> ans(n, vector<int>(n, 0));\n\n        unordered_map<int, int> mp;\n        \n        for(int i=0; i<topo1.size(); i++){\n            mp[topo1[i]] = i;\n        }\n        \n        for(int i=0; i<topo2.size(); i++){\n            ans[mp[topo2[i]]][i] = topo2[i];\n        }\n        \n        return ans;\n    }\n    \n    vector<vector<int>> buildMatrix(int n, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        \n        graph g1(n+1), g2(n+1);\n        \n        g1.make_adj(rowConditions);\n        g2.make_adj(colConditions);\n                \n        vector<int> topo1 = g1.kahn_algo(), topo2 = g2.kahn_algo();\n        \n        return solve(n, topo1, topo2);        \n    }\n};\n```\n\nPlease upvote if you find it helpful :)
['Breadth-First Search', 'Graph', 'Topological Sort', 'C']