[Python3] Topological Sort - Simple Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nFind the order for row and col respectively and then assign them to the m
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nFind the order for row and col respectively and then assign them to the matrix. Note that there are only `k` number need to assign which is also the side of square matrix. Thus we can assign each number in each unique row and col\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(M + N)$$ with `N` is number of `rowConditions` and `M` is number of `colConditions`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(k)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def buildMatrix(self, k: int, rowConditions: List[List[int]], colConditions: List[List[int]]) -> List[List[int]]:\n        matrix = [[0 for _ in range(k)] for _ in range(k)]\n        \n        def topo_sort(condition: List[List[int]]) -> dict:\n            order = {}\n            in_degree = [0 for _ in range(k)]\n            g = collections.defaultdict(list)\n            for start, end in condition:\n                g[start - 1].append(end - 1)\n                in_degree[end - 1] += 1\n            \n            dq = collections.deque()\n            for i in range(k):\n                if in_degree[i] == 0: dq.append(i)\n            \n            i = 0\n            while dq:\n                u = dq.popleft()\n                order[u] = i\n                for v in g[u]:\n                    in_degree[v] -= 1\n                    if in_degree[v] == 0: dq.append(v)\n                i += 1\n            \n            return order\n        \n        row_order, col_order = topo_sort(rowConditions), topo_sort(colConditions)\n        if len(row_order) != k or len(col_order) != k: return []\n        for u in row_order:\n            r, c = row_order[u], col_order[u]\n            matrix[r][c] = u + 1\n        return matrix\n```
['Greedy', 'Graph', 'Topological Sort', 'Matrix', 'Python3']