순서가 정해져있는 작업을 차례대로 수행할 때 그 순서를 결정해주기 위해 사용하는 알고리즘
DAG(Directed Acyclic Graph)
비순환 그래프여야 하며 시작점이 있어야 한다.
Queue, stack으로 구현
O(V + E)
import Foundation
let input = readLine()!.split(separator: " ").map({ Int(String($0))! })
let n = input[0]
let t = input[1]
var adj = Array(repeating: [Int](), count: n+1)
var inDegree = Array(repeating: 0, count: n+1) // 진입차수
for _ in 0..<t {
let input = readLine()!.split(separator: " ").map({ Int(String($0))! })
let v = input[0]
let w = input[1]
adj[v].append(w)
inDegree[w] += 1
}
var queue = [Int]()
for i in 1..<n+1 {
if inDegree[i] == 0 {
queue.append(i)
}
}
for _ in 1..<n+1 {
if queue.isEmpty {
print("이건 위상정렬 쓰면 안됨니다🚥")
break
}
let x = queue.removeFirst()
print(x)
for j in 0..<adj[x].count {
let y = adj[x][j]
inDegree[y] -= 1
if inDegree[y] == 0 {
queue.append(y)
}
}
}
아마
let input = readLine()!.split(separator: " ").map({ Int(String($0))! })
let n = input[0]
let t = input[1]
var adj = Array(repeating: Array(repeating: 0, count: n+1), count: n+1)
var visited = Array(repeating: false, count: n+1)
for _ in 0..<t {
let input = readLine()!.split(separator: " ").map({ Int(String($0))! })
let v = input[0]
let w = input[1]
adj[v].append(w)
}
var result = [Int]()
var stack = [Int]()
func dfs(_ i: Int) {
visited[i] = true
for j in 1..<adj[i].count {
let next = adj[i][j]
if !visited[next] {
dfs(next)
}
}
stack.append(i)
}
for i in 1..<n+1 {
if !visited[i] {
dfs(i)
}
}
while stack.count > 1 {
print(stack.popLast()!)
}