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
}