[LeetCode The Hard Way] Kahn's Algorithm with Explanation
Please check out LeetCode The Hard Way for more solution explanations and tutorials. If you like it, please give a star and watch my Github Repository.\n\n---\n
Please check out [LeetCode The Hard Way](https://wingkwong.github.io/leetcode-the-hard-way/) for more solution explanations and tutorials. If you like it, please give a star and watch my [Github Repository](https://github.com/wingkwong/leetcode-the-hard-way).\n\n---\n\n```cpp\nclass Solution {\npublic:\n    // there is at least one vertex in the \u201Cgraph\u201D with an \u201Cin-degree\u201D of 0. \n    // if all vertices in the \u201Cgraph\u201D have non-zero \u201Cin-degree\u201D, \n    // then all vertices need at least one vertex as a predecessor. \n    // In this case, no vertex can serve as the starting vertex.\n    template<typename T_vector, typename T_vector_vector>\n      T_vector kahn(int n, T_vector_vector &edges){\n          vector<int> ordering, indegree(n, 0);\n          vector<vector<int> > g(n);\n          for (auto e : edges) {\n            --e[0], --e[1];\n            indegree[e[1]]++;\n            g[e[0]].push_back(e[1]);\n          }\n          queue<int> q;\n          for (int i = 0; i < n; i++) if (indegree[i] == 0) q.push(i);\n          int visited = 0;\n          while (!q.empty()) {\n            int u = q.front(); q.pop();\n            ordering.push_back(u);\n            visited++;\n            for (auto v : g[u]) {\n              if (--indegree[v] == 0) q.push(v);\n            }\n          }\n          if (visited != n) return T_vector{};\n          return ordering;\n      }\n    \n    // the idea is to topologically sort rowConditions & colConditions\n    // then build the final matrix based on the order if possible\n    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        vector<vector<int>> ans(k, vector<int>(k));\n        // in example 1, rowOrders would be [1, 3, 2]\n        vector<int> rowOrders = kahn<vector<int>>(k, rowConditions);\n        // in example 1, colOrders would be [3, 2, 1]\n        vector<int> colOrders = kahn<vector<int>>(k, colConditions);\n        // since we need to map to a `k x k` matrix, \n        // we need to make sure that both got exact k elements\n        if ((int) rowOrders.size() == k && (int) colOrders.size() == k) {\n            // used to map the index of the given row / col value\n            // i.e. given the value, which row / col idx should it belong to\n            vector<int> rowIdx(k), colIdx(k);\n            for (int i = 0; i < k; i++) rowIdx[rowOrders[i]] = i, colIdx[colOrders[i]] = i;\n            // update the final matrix\n            for (int i = 0; i < k; i++) ans[rowIdx[i]][colIdx[i]] = i + 1;\n            return ans;\n        }\n        // else we don\'t have a matrix that satisfies the conditions\n        return vector<vector<int>>{};\n    }\n};\n```
['Breadth-First Search', 'Topological Sort', 'C', 'C++']