2192. All Ancestors of a Node in a Directed Acyclic Graph
一個有向無環圖(Directed Acyclic Graph)有n個節點
並且給一個2D矩陣edges:edges[i]=[from_i,to_i]表示兩點之間的邊
請回傳每個節點的祖先，並且以遞增的順序排列
思路：
原本想說從根節點開始dfs下去，不過會TLE
後來改個方法從子節點開始往上紀錄
先用一個2D矩陣紀錄每個節點的parent node
接著將0~N-1丟到dfs function去紀錄每個祖先
要紀錄已經拜訪過的節點，不要重複拜訪
因為題目要求要排序，所以乾脆開一個n*n矩陣visit
visit[i][j]代表第j個節點是否為i的祖先
這樣可以防止重複拜訪，之後又可以不用排序
應該有更快的方法，不過我想不到
golang code :
func getAncestors(n int, edges [][]int) [][]int {
rec := make([][]int, n)
res := make([][]int, n)
visit := make([][]bool, n)
for _, val := range edges {
rec[val[1]] = append(rec[val[1]], val[0])
}
var dfs func(int, int)
dfs = func(root int, prev int) {
if !visit[root][prev] {
visit[root][prev] = true
for _, val := range rec[prev] {
dfs(root, val)
}
}
}
for i := 0; i < n; i++ {
visit[i] = make([]bool, n)
for j := 0; j < len(rec[i]); j++ {
dfs(i, rec[i][j])
}
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if visit[i][j] == true {
res[i] = append(res[i], j)
}
}
}
return res
}