Swift | DFS Topological Sort (+ Kahn)
I originally wrote this using DFS Topological Sort (dfsSort()) but I\'m adding Kahn\'s Topological Sort (khansSort()) for comparison, since most solutions use t
I originally wrote this using **DFS Topological Sort** (```dfsSort()```) but I\'m adding **Kahn\'s Topological Sort** (```khansSort()```) for comparison, since most solutions use that algorithm.\n\nAsymptotically, they both run in O(V + E) time and in practice they seem roughly equivalent.\n\nI thought that one may be easier to implement than the other one, but I also find them to be approximately equal from that point of view.\n\n# Code\n```\nclass Solution {\n    func buildMatrix(_ k: Int, _ rowConditions: [[Int]], _ colConditions: [[Int]]) -> [[Int]] {\n        var matrix = Array(repeating: Array(repeating: 0, count: k), count: k)\n        guard let sortedRows = Graph(nodes: Array(1...k), edges: rowConditions).dfsSort(),\n              let sortedCols = Graph(nodes: Array(1...k), edges: colConditions).kahnsSort()\n        else { return [] }\n\n        for num in 1...k {\n            if let row = sortedRows.firstIndex(of: num), let col = sortedCols.firstIndex(of: num) {\n                matrix[row][col] = num\n            }\n        }\n\n        return matrix\n    }\n}\n\nclass Graph {\n    private let nodes: [Int]\n    private let edges: [[Int]]\n    private var adj = [Int: [Int]]()\n\n    init(nodes: [Int], edges: [[Int]]) {\n        self.nodes = nodes\n        self.edges = edges\n        for edge in edges {\n            adj[edge[0], default: []].append(edge[1])\n        }\n    }\n\n    func dfsSort() -> [Int]? {\n        enum NodeState { case visited, visiting, unvisited }\n        var nodeState = [Int: NodeState]()\n        var stack: [Int] = []\n\n        for node in nodes { nodeState[node] = .unvisited }\n        for node in nodes {\n            if !dfs(node) {\n                return nil\n            }\n        }\n        \n        return stack.reversed()\n    \n        func dfs(_ node: Int) -> Bool {\n            if let state = nodeState[node], state == .visited { return true }\n            if let state = nodeState[node], state == .visiting { return false }\n            nodeState[node] = .visiting\n        \n            if let neighbors = adj[node] {\n                for neighbor in neighbors {\n                    if !dfs(neighbor) { return false }\n                }\n            }\n        \n            nodeState[node] = .visited\n            stack.append(node)\n            return true\n        }      \n    }\n\n    func kahnsSort() -> [Int]? {\n        var sorted: [Int] = []\n        var inDegrees: [Int: Int] = Dictionary(uniqueKeysWithValues: nodes.map { ($0, 0) })\n        for edge in edges {\n            inDegrees[edge[1], default: 0] += 1\n        }\n        var stack = inDegrees.filter{ $0.1 == 0 }.map { $0.0 }\n\n        while let node = stack.popLast() {\n            if let neighbors = adj[node] {\n                for neighbor in neighbors {\n                    inDegrees[neighbor, default: 0] -= 1\n                    if inDegrees[neighbor] == 0 { stack.append(neighbor) }\n                }\n            }\n            sorted.append(node)\n        }\n\n        return sorted.count == nodes.count ? sorted : nil\n    }\n}\n```
['Swift']