✅✅Faster || Easy To Understand || C++ Code
Using Topological Sort With BFS\n\n Time Complexity :- O(V + E)\n\n Space Complexity :- O(V + E)\n\n\nclass Solution {\npublic:\n    \n    // function for findi
* ***Using Topological Sort With BFS***\n\n* ***Time Complexity :- O(V + E)***\n\n* ***Space Complexity :- O(V + E)***\n\n```\nclass Solution {\npublic:\n    \n    // function for finding toposort of a graph\n    \n    vector<int> toposort(vector<vector<int>> adj)\n    {\n        int V = adj.size();\n        \n        // find the indegree of every node\n        \n        vector<int> indegree(V, 0);\n        \n        for(int u = 0; u < V; u++)\n        {\n            for(auto v : adj[u])\n            {\n                indegree[v]++;\n            }\n        }\n        \n        // res will store the toposort order of graph\n        \n        vector<int> res;\n        \n        // push the node with indegree = 0 into q\n        \n        queue<int> q;\n        \n        for(int u = 0; u < V; u++)\n        {\n            if(indegree[u] == 0)\n            {\n                q.push(u);\n            }\n        }\n        \n        while(!q.empty())\n        {\n            int size = q.size();\n            \n            for(int k = 0; k < size; k++)\n            {\n                int u = q.front();\n                \n                q.pop();\n                \n                res.push_back(u);\n                \n                // go to adjacent nodes\n                \n                for(auto v : adj[u])\n                {\n                    indegree[v]--;\n                    \n                    if(indegree[v] == 0)\n                    {\n                        q.push(v);\n                    }\n                }\n            }\n        }\n        \n        // res.size() != V, it means there is cycle\n        \n        if(res.size() != V)\n            return {};\n        \n        return res;\n    }\n    \n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        \n        int n = rowConditions.size();\n        \n        int m = colConditions.size();\n        \n        // create two adjacency list one for rowConditions and other for colConditions\n        \n        vector<vector<int>> adj_r(k);\n        \n        vector<vector<int>> adj_c(k);\n        \n        for(int i = 0; i < n; i++)\n        {\n            int u = rowConditions[i][0];\n            \n            int v = rowConditions[i][1];\n            \n            adj_r[u - 1].push_back(v - 1);\n        }\n        \n        for(int i = 0; i < m; i++)\n        {\n            int u = colConditions[i][0];\n            \n            int v = colConditions[i][1];\n            \n            adj_c[u - 1].push_back(v - 1);\n        }\n        \n        // call for toposort\n        \n        vector<int> row = toposort(adj_r);\n        \n        if(row.size() == 0)\n        {\n            return {};\n        }\n        \n        // call for toposort\n        \n        vector<int> col = toposort(adj_c);\n        \n        if(col.size() == 0)\n        {\n            return {};\n        }\n        \n        // create matrix\n        \n        // store the index of number of col in mp array\n        \n        vector<int> mp(k, 0);\n        \n        for(int i = 0; i < col.size(); i++)\n        {\n            mp[col[i]] = i;\n        }\n        \n        vector<vector<int>> res(k, vector<int> (k, 0));\n        \n        for(int i = 0; i < row.size(); i++)\n        {\n            // find the val\n            \n            int val = row[i] + 1;\n            \n            // find the row and col\n            \n            int r = i;\n            \n            int c = mp[row[i]];\n            \n            // put in res matrix\n            \n            res[r][c] = val;\n        }\n        \n        return res;\n    }\n};\n```
['Breadth-First Search', 'Graph', 'Topological Sort', 'C', 'C++']