Python | Topological Sorting
see the Successfully Accepted Submission\n\n# Code\n\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[Lis
[see the Successfully Accepted Submission](https://leetcode.com/problems/build-a-matrix-with-conditions/submissions/1328224805/?envType=daily-question&envId=2024-07-21)\n\n# Code\n```\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n        def topological_sort(conditions):\n            graph = defaultdict(list)\n            indegree = {i: 0 for i in range(1, k + 1)}\n            \n            for u, v in conditions:\n                graph[u].append(v)\n                indegree[v] += 1\n            \n            zero_indegree = deque([i for i in range(1, k + 1) if indegree[i] == 0])\n            order = []\n            \n            while zero_indegree:\n                node = zero_indegree.popleft()\n                order.append(node)\n                \n                for neighbor in graph[node]:\n                    indegree[neighbor] -= 1\n                    if indegree[neighbor] == 0:\n                        zero_indegree.append(neighbor)\n            \n            if len(order) != k:\n                return []\n            \n            return order\n        \n        row_order = topological_sort(rowConditions)\n        if not row_order:\n            return []\n        \n        col_order = topological_sort(colConditions)\n        if not col_order:\n            return []\n        \n        row_pos = {num: i for i, num in enumerate(row_order)}\n        col_pos = {num: i for i, num in enumerate(col_order)}\n        \n        matrix = [[0] * k for _ in range(k)]\n        \n        for num in range(1, k + 1):\n            matrix[row_pos[num]][col_pos[num]] = num\n        \n        return matrix\n\n```\n\n# Steps\n\n## Topological Sorting\n\nFirst, we need to determine the order of the numbers for the rows and columns separately using the given conditions.\n\n## Matrix Construction\n\nUsing the sorted orders, we can then construct the matrix such that each number appears exactly once and the constraints are satisfied.\n\n# Step-by-step Approach\n\n## Topological Sorting for Rows and Columns\n\n- We need to perform a topological sort on the row conditions to determine the order in which the numbers should appear in the rows.\n- Similarly, we need to perform a topological sort on the column conditions to determine the order in which the numbers should appear in the columns.\n- If either of the conditions forms a cycle, it\'s impossible to satisfy the constraints, and we should return an empty matrix.\n\n## Construct the Matrix\n\nUsing the sorted orders from the topological sorts, place the numbers in their respective positions in a \\(k \\times k\\) matrix.\n\n# Explanation of the Code\n\n## Topological Sort Function\n\n- We create a graph and an in-degree count for each number.\n- We iterate through the conditions to build the graph and update the in-degree of each node.\n- We use a deque to process nodes with zero in-degree, appending them to the sorted order and reducing the in-degree of their neighbors.\n- If we process all numbers and the sorted order contains all \\(k\\) numbers, we return the order; otherwise, a cycle is present, and we return an empty list.\n\n## Building the Matrix\n\n- We get the row and column orders from the topological sort.\n- If either order is empty, we return an empty matrix.\n- We map each number to its position in the row and column orders.\n- We construct the matrix by placing each number at its corresponding position based on the sorted orders.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']