題目
給有向圖,找出是否有「環 Cycle」存在
範例: v1 v2: 表示 v1 指向 v2 0 1 0 2 0 5 1 2 1 3 2 3 4 0 5 4 return true
思路
用 DFS 走訪每個點,再用 array(以下程式碼用 recTraverse) 記錄每個點走訪,當二次走到時就代表有 cycle 了
程式碼
class Solution {
let count: Int
var adjList = [[Int]]()
init(count:Int) {
self.count = count
for _ in 0..<count {
adjList.append([])
}
}
func addEdge(v:Int, w:Int) {
adjList[v].append(w) // Add w to v’s list.
}
func isCyclicUtil(_ v:Int, _ visited:inout [Bool], _ recTraverse: inout[Bool]) -> Bool {
if visited[v] == false {
// Mark the current node as visited and part of recursion stack
visited[v] = true
recTraverse[v] = true
for i in adjList[v] {
print("traverse from \(v) -> \(i)")
if !visited[i] && isCyclicUtil(i, &visited, &recTraverse) {
return true
} else if recTraverse[i] == true{
return true
}
}
}
recTraverse[v] = false // remove the vertex from recursion stack
return false
}
func isCyclic() -> Bool {
var visited:[Bool] = Array(repeating: false, count: count)
var stack:[Bool] = Array(repeating: false, count: count)
for i in 0..<count {
if !visited[i] && isCyclicUtil(i, &visited, &stack) {
return true
}
}
return false
}
}
var s = Solution(count: 6)
s.addEdge(v: 0, w: 1)
s.addEdge(v: 0, w: 2)
s.addEdge(v: 0, w: 5)
s.addEdge(v: 1, w: 2)
s.addEdge(v: 1, w: 3)
s.addEdge(v: 2, w: 3)
s.addEdge(v: 4, w: 0)
s.addEdge(v: 5, w: 4)
s.isCyclic() // true 0->5->4->0