Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

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
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.160.103 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719677063.A.81C.html
推 sustainer123: 大師