Kahn's topo sort/DFS rows & cols build matrix||66ms Beats 99.72%
Intuition\n Describe your first thoughts on how to solve this problem. \nUse Kahn\'s algorthm, topological sort.\nApply for rowConditions, rowConditions to find
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse Kahn\'s algorthm, topological sort.\nApply for rowConditions, rowConditions to find the ordering in row & in col.\nThen find pos (i, j) for x where 1<=x<=k\n\n2nd approach uses DFS+degree as visited instead of Kahn\'s algorithm. Moreover the output for the recursive function `f(int i)` is using `std::deque<int>` for push front the number `i` for avoiding of reversing the container.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTopological sort can solve the following questions\n[2192. All Ancestors of a Node in a Directed Acyclic Graph](https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/solutions/5385071/topo-sort-kahn-s-algo-counting-sort-54ms-beats-100/)\n[207. Course Schedule](https://leetcode.com/problems/course-schedule/solutions/3756937/w-explanation-c-dfs-vs-bfs-kahn-s-algorithm/)\n[210. Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)\n[1203. Sort Items by Groups Respecting Dependencies\n](https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/solutions/3933825/c-using-bfs-kahn-s-algorithm-vs-dfs-beats-97-67/)\n[1203. Sort Items by Groups Respecting Dependencies| Please Turn English Subtitles if Neceesary]\n[https://youtu.be/vdar3a_ZdCI](https://youtu.be/vdar3a_ZdCI)\nKahn\'s Algorithm is BFS method by removing the edges and decreasing the indegrees. \n1. Use Kahn\'salgorithm to define the function `vector<int> topo_sort(int k, vector<vector<int>>& conditions)`\n2. apply `order_row=topo_sort(k, rowConditions)`, `order_col=topo_sort(k, colConditions)`\n3. If `order_row.empty()|| order_col.empty()` some conflicts occur then return the empty array\n4. The rest is to build the answering matrix `arr`, to find pos (i, j) for each integer x where 1<=x<=k\n5. Use single for-loop to compute pos_i, pos_j & set `arr[pos_i[x]][pos_j[x]]=x`\n6.  `arr` is the answer\n7. 2nd approach uses DFS+degree as visited instead of Kahn\'s algorithm. Moreover the output for the recursive function `f(int i)` is using `std::deque<int>` for push front the number `i` for avoiding of reversing the container.\n\n# Real RUN for testcase\n2 different approaches have different results; both are correct. Consider the testcase\n```\n8\n[[1,2], [1, 8]]\n[[5,7],[2,7],[4,3],[6,7],[4,3],[2,3],[6,2]]\n```\n![DAG.png](https://assets.leetcode.com/users/images/d9085b6d-1fa5-408d-8cae-f27843b92976_1721557070.0269687.png)\n\nUse topo_sort, one has\n```\norder_row=[   1   3   4   5   6   7   2   8]\norder_col=[   1   4   5   6   8   2   7   3]\n\narr=\n[   1   0   0   0   0   0   0   0]\n[   0   0   0   0   0   0   0   3]\n[   0   4   0   0   0   0   0   0]\n[   0   0   5   0   0   0   0   0]\n[   0   0   0   6   0   0   0   0]\n[   0   0   0   0   0   0   7   0]\n[   0   0   0   0   0   2   0   0]\n[   0   0   0   0   8   0   0   0]\n```\nUse dfs, one has\n```\norder_row=[   7   6   5   4   3   1   8   2]\norder_col=[   8   6   2   5   7   4   3   1]\n\narr=\n[   0   0   0   0   0   0   7   0]\n[   0   6   0   0   0   0   0   0]\n[   0   0   5   0   0   0   0   0]\n[   0   0   0   4   0   0   0   0]\n[   0   0   0   0   0   3   0   0]\n[   0   0   0   0   0   0   0   1]\n[   8   0   0   0   0   0   0   0]\n[   0   0   0   0   2   0   0   0]\n\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(k^2+|rowConditions|+|rowConditions|)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n $$O(k)$$ \n# Code|C++ 72ms Beats 99.72%\n```\nclass Solution {\npublic:\n    //topological sort using BFS (Kahn\'s algorithm)\n    static vector<int> topo_sort(int k, vector<vector<int>>& conditions){\n        vector<int> deg(k+1, 0);\n        vector<vector<int>> adj(k+1);\n        for(auto& edge: conditions){\n            int v=edge[0], w=edge[1];\n            adj[v].push_back(w);\n            deg[w]++;\n        }\n        queue<int> q;\n        for (int i = 1; i<=k; i++) {\n            if (deg[i] == 0) \n                q.push(i);\n        }\n\n        int count=0;\n        vector<int> ans;\n        ans.reserve(k);\n        while(!q.empty()){\n            int j=q.front();\n            q.pop();\n            ans.push_back(j);\n            count++;\n            for(int k:adj[j]){\n                deg[k]--;\n                if (deg[k] == 0) {\n                    q.push(k);\n                }\n            }\n        }\n        if(count != k) return {};// has cycle\n        else return ans ;\n\n    }\n\n    static void print(auto& c){\n        cout<<"[";\n        for(int x: c){\n            cout<<x;\n            if (x!=c.back()) cout<<", ";\n        }\n        cout<<"]\\n";\n    }\n\n    static vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {\n        auto order_row=topo_sort(k, rowConditions);\n        auto order_col=topo_sort(k, colConditions);\n\n    //  print out the ordering in row & in col\n    //    print(order_row), print(order_col);\n\n        if (order_row.empty()|| order_col.empty())\n            return {};// some conflict\n\n        vector<vector<int>> arr(k, vector<int>(k));\n        // Find pos for x where 1<=x<=k\n        vector<int> pos_i(k+1, -1), pos_j(k+1, -1);\n        for(int i=0; i<k; i++){\n            pos_i[order_row[i]]=i;\n            pos_j[order_col[i]]=i;\n        }\n\n        for(int x=1; x<=k; x++)\n            arr[pos_i[x]][pos_j[x]]=x;\n        \n        return arr;\n    }\n};\n\n\n\n\nauto init = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return \'c\';\n}();\n```\n# revised DFS+ deg as visited+ detect cycle||69ms beats 99.72%\n\nThere are some other versions.\n```\n    //DFS+ degree as visited\n    static deque<int> dfs(int k, vector<vector<int>>& conditions) {\n        vector<int> deg(k + 1, 0);\n        vector<vector<int>> adj(k + 1);\n        for (auto& edge : conditions) {\n            int v = edge[0], w = edge[1];\n            adj[v].push_back(w);\n            deg[w]++;\n        }\n\n        deque<int> ans;\n        bool hasCycle= 0;\n        // Use deg >=0 :unvisited, -1 = visiting, -2= visited\n        function<void(int)> f = [&](int i) -> void {\n            if (hasCycle) return;\n\n            deg[i] = -1; // mark as visiting\n            for (int j : adj[i]) {\n                if (deg[j] >= 0) { // not visited\n                    f(j);\n                } \n                else if (deg[j]==-1) { //in the current path, so a cycle\n                    hasCycle = 1;\n                    return;\n                }\n            }\n            deg[i]=-2; // mark as visited\n            ans.push_front(i);\n        };\n\n        for (int i = 1; i <= k; i++) {\n            if (deg[i]>=0) {\n                f(i);\n                if (hasCycle) return {}; // cycle detected\n            }\n        }\n        return ans;\n    }\n\n```\n
['Array', 'Depth-First Search', 'Breadth-First Search', 'Graph', 'Topological Sort', 'Matrix', 'C++']