javascript 解法, 执行用时: 311 ms, 内存消耗: 76.8 MB, 提交时间: 2024-04-04 18:14:26

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[][]}
 */
var getAncestors = function(n, edges) {
    const g = Array.from({length: n}, () => []);
    for (const [x, y] of edges) {
        g[y].push(x); // 反向建图
    }

    function dfs(x) {
        vis[x] = true; // 避免重复访问
        for (const y of g[x]) {
            if (!vis[y]) {
                dfs(y, g, vis); // 只递归没有访问过的点
            }
        }
    }
    const ans = Array.from({length: n}, () => []);
    const vis = Array(n);
    for (let i = 0; i < n; i++) {
        vis.fill(false);
        dfs(i); // 从 i 开始 DFS
        vis[i] = false; // ans[i] 不含 i
        for (let j = 0; j < n; j++) {
            if (vis[j]) {
                ans[i].push(j);
            }
        }
    }
    return ans;
};

javascript 解法, 执行用时: 263 ms, 内存消耗: 79.7 MB, 提交时间: 2024-04-04 18:14:08

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[][]}
 */
var getAncestors = function(n, edges) {
    const g = Array.from({length: n}, () => []);
    for (const [x, y] of edges) {
        g[x].push(y);
    }

    function dfs(x) {
        vis[x] = start; // 避免重复访问
        for (const y of g[x]) {
            if (vis[y] !== start) {
                ans[y].push(start); // start 是访问到的点的祖先
                dfs(y); // 只递归没有访问过的点
            }
        }
    }
    const ans = Array.from({length: n}, () => []);
    const vis = Array(n).fill(-1);
    let start = 0;
    for (; start < n; start++) {
        dfs(start); // 从 start 开始 DFS
    }
    return ans;
};

rust 解法, 执行用时: 57 ms, 内存消耗: 8.5 MB, 提交时间: 2024-04-04 18:13:54

impl Solution {
    pub fn get_ancestors(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = n as usize;
        let mut g = vec![vec![]; n];
        for e in &edges {
            g[e[0] as usize].push(e[1] as usize);
        }

        fn dfs(x: usize, start: usize, g: &Vec<Vec<usize>>, vis: &mut Vec<usize>, ans: &mut Vec<Vec<i32>>) {
            vis[x] = start; // 避免重复访问
            for &y in &g[x] {
                if vis[y] != start {
                    ans[y].push(start as i32); // start 是访问到的点的祖先
                    dfs(y, start, g, vis, ans); // 只递归没有访问过的点
                }
            }
        }
        let mut ans = vec![vec![]; n];
        let mut vis = vec![n; n];
        for start in 0..n {
            dfs(start, start, &g, &mut vis, &mut ans); // 从 start 开始 DFS
        }
        ans
    }
}

rust 解法, 执行用时: 68 ms, 内存消耗: 8.6 MB, 提交时间: 2024-04-04 18:13:41

impl Solution {
    pub fn get_ancestors(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = n as usize;
        let mut g = vec![vec![]; n];
        for e in &edges {
            g[e[1] as usize].push(e[0] as usize); // 反向建图
        }

        fn dfs(x: usize, g: &Vec<Vec<usize>>, vis: &mut Vec<bool>) {
            vis[x] = true; // 避免重复访问
            for &y in &g[x] {
                if !vis[y] {
                    dfs(y, g, vis); // 只递归没有访问过的点
                }
            }
        }
        let mut ans = vec![vec![]; n];
        let mut vis = vec![false; n];
        for i in 0..n {
            vis.fill(false);
            dfs(i, &g, &mut vis); // 从 i 开始 DFS
            vis[i] = false; // ans[i] 不含 i
            for (j, &b) in vis.iter().enumerate() {
                if b {
                    ans[i].push(j as i32);
                }
            }
        }
        ans
    }
}

golang 解法, 执行用时: 124 ms, 内存消耗: 20.4 MB, 提交时间: 2023-10-26 23:54:32

func getAncestors1(n int, edges [][]int) [][]int {
    // (孩子)1->2(父亲)
    g := make([][]int, n)//孩子的父亲数组
    fres := make([]map[int]bool, n)//父亲的孩子字典
    for i:=range fres{
        fres[i] = make(map[int]bool)
    }
    in := make([]int, n)//入度
    for _,e := range edges{
        g[e[0]] = append(g[e[0]], e[1])
        fres[e[1]][e[0]] = true
        in[e[1]]++
    }
    // 拓扑排序模板
    q:=[]int{}
    for i:=0; i<n; i++{
        if in[i] == 0{q=append(q, i)}
    }
    for len(q)>0{
        u := q[0]
        q = q[1:]
        for _,v := range g[u]{
            //将孩子的字典合并到父亲
            for k := range fres[u]{
                fres[v][k] = true
            }
            in[v]--
            if in[v] == 0{
                q = append(q, v)    
            }
        }
    }

    res := make([][]int, n)
    for i:=range res{
        for j:=0; j<=1000; j++{//顺序输出
            if fres[i][j]{
                res[i] = append(res[i], j)
            }
        }
    }
    return res
}

func getAncestors2(n int, edges [][]int) [][]int {
    g:=make([][]int, n)
    // 存孩子节点数组
    for _,e :=range edges{
        g[e[1]] = append(g[e[1]], e[0])
    }
    res := make([][]int, n)
    m := make([]bool, n)
    temp := []int{}
    var dfs func(u int)
    dfs = func(u int){
        for _,v := range g[u]{
            if !m[v]{
                m[v] = true
                temp = append(temp, v)
                dfs(v)
            }
        }
    }
    for i:=0; i<n; i++{
        // 每次重置map和临时的一行数据
        m = make([]bool, n)
        temp = []int{}
        dfs(i)
        res[i] = temp
        sort.Ints(res[i])
    }
    return res
}

func getAncestors(n int, edges [][]int) [][]int {
    // 保存每个父节点，bfs
    res := make([][]int, n)
    g := make([][]int, n)
    for _,e :=range edges{
        g[e[1]] = append(g[e[1]], e[0])
    }
    for i:= 0; i<n; i++{
        q := []int{i}
        m := make([]bool, n)
        for len(q)>0{
            u := q[0]; q=q[1:]
            for _, v := range g[u]{
                if !m[v]{
                    q = append(q, v)
                    res[i] = append(res[i], v)
                    m[v] = true
                }
            }
        }
        sort.Ints(res[i])
    }
    return res
}

python3 解法, 执行用时: 112 ms, 内存消耗: 47.2 MB, 提交时间: 2023-10-26 23:53:36

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        
        graph = collections.defaultdict(list)
        indeg = collections.defaultdict(int)
        for u, v in edges:
            graph[u].append(v)      # 建图
            indeg[v] += 1           # 统计入度
        
        deque = collections.deque([u for u in range(n) if indeg[u]==0])     # 入度为0的节点入列
        res = [set() for _ in range(n)]     # set可去重
        while deque:
            u = deque.popleft()         # 题目保证无环，故每个节点只会入列一次
            for v in graph[u]:
                res[v].add(u)           # 父节点u加入结果中
                res[v].update(res[u])   # 直接利用父节点u的祖先信息，减少重复计算
                indeg[v] -= 1           # 入度-1
                if indeg[v] == 0:       # 入度为0的节点入列
                    deque.append(v)
        
        return [sorted(rs) for rs in res]

python3 解法, 执行用时: 128 ms, 内存消耗: 47.1 MB, 提交时间: 2023-10-26 23:53:25

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        anc = [set() for _ in range(n)]   # 存储每个节点祖先的辅助数组
        e = [[] for _ in range(n)] # 邻接表
        indeg = [0] * n   # 入度表
        # 预处理
        for u, v in edges:
            e[u].append(v)
            indeg[v] += 1
        # 广度优先搜索求解拓扑排序
        q = deque()
        for i in range(n):
            if indeg[i] == 0:
                q.append(i)
        while q:
            u = q.popleft()
            for v in e[u]:
                # 更新子节点的祖先哈希表
                anc[v].add(u)
                anc[v].update(anc[u])
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        # 转化为答案数组
        res = [sorted(anc[i]) for i in range(n)]        
        return res

cpp 解法, 执行用时: 480 ms, 内存消耗: 143.3 MB, 提交时间: 2023-10-26 23:53:07

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<unordered_set<int>> anc(n);   // 存储每个节点祖先的辅助数组
        vector<vector<int>> e(n);   // 邻接表
        vector<int> indeg(n);   // 入度表
        // 预处理
        for (const auto& edge: edges) {
            e[edge[0]].push_back(edge[1]);
            ++indeg[edge[1]];
        }
        // 广度优先搜索求解拓扑排序
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (!indeg[i]) {
                q.push(i);
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v: e[u]) {
                // 更新子节点的祖先哈希表
                anc[v].insert(u);
                for (int i: anc[u]) {
                    anc[v].insert(i);
                }
                --indeg[v];
                if (!indeg[v]) {
                    q.push(v);
                }
            }
        }
        // 转化为答案数组
        vector<vector<int>> res(n);
        for (int i = 0; i < n; ++i) {
            for (int j: anc[i]) {
                res[i].push_back(j);
            }
            sort(res[i].begin(), res[i].end());
        }
        return res;
    }
};

java 解法, 执行用时: 193 ms, 内存消耗: 61.9 MB, 提交时间: 2023-10-26 23:52:50

class Solution {
    /*
    逆向思维:建立反向图+dfs求x的叶子结点
    */
    /*有向图类DiGraph*/
    class DiGraph {
        // 顶点个数
        int V;
        // 邻接表key->list(...)
        Map<Integer, List<Integer>> adj;

        // 构造器
        public DiGraph(int _V) {
            V = _V;
            adj = new HashMap<>();
        }

        // 获取节点x的邻接表
        public List<Integer> getAdj(int x) {
            if(!adj.containsKey(x)) {
                adj.put(x, new ArrayList<>());
            }
            return adj.get(x);
        }

        // 添加边(v->w)
        public void addEdge(int v, int w) {
            if(!adj.containsKey(v)) {
                adj.put(v, new ArrayList<>());
            }
            adj.get(v).add(w);
        }

        // 将图的边取反
        public DiGraph reverse() {
            DiGraph dg = new DiGraph(this.V);
            for(int key : this.adj.keySet()) {
                for(int w : this.adj.get(key)) {
                    dg.addEdge(w, key);
                }   
            }
            return dg;
        }
    }

    // 全局变量visited:用于记录dfs过程中是否访问过该节点
    boolean[] visited;
    // 全局反向图
    DiGraph rg;
    /*主函数:获取n个节点的祖先节点*/
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> res = new ArrayList<>();
        // 根据edges建图
        DiGraph dg = new DiGraph(n);
        // 添加边
        for(int[] edge : edges) {
            dg.addEdge(edge[0], edge[1]);
        }
        // 将dg反向
        rg = dg.reverse();
        // 求每个节点的叶子节点
        for(int i = 0; i < n; i++) {
            // set存储节点i的叶子结点
            Set<Integer> set = new TreeSet<>();
            // 重置标记
            visited = new boolean[n];
            // 通过dfs方式将节点i的叶子节点添加到set中去(自动排序)
            getDes(i, set);
            // 将set添加到res中
            res.add(new ArrayList<>(set));
        }
        return res;
    }

    /*dfs求某个节点x的叶子结点*/
    private void getDes(int x, Set<Integer> set) {
        // 标记节点x被访问过避免重复访问
        visited[x] = true;
        // 遍历节点x的邻接表
        for(int son : rg.getAdj(x)) {
            // 若x的son没有被访问过
            if(!visited[son]) {
                // son加入set
                set.add(son);
                // 递归求son的叶子结点加入set
                getDes(son, set);
            }
        }
    }
}

java 解法, 执行用时: 157 ms, 内存消耗: 78.9 MB, 提交时间: 2023-10-26 23:52:38

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
    /*
    尝试:DFS+TreeSet(超时)
    参考评论区思路:拓扑排序(与课程表那一题类似)
    1.构造每个节点的入度数组以及邻接表
    2.用<List<List<Integer>>> res存储结果,List<Set<Integer>> tmp 存储每个节点的祖先节点(自动排序)
    3.构造入度数组时填充好res与tmp的n个空位,同时将入度为0的节点入队初始化队列
    4.循环将每个节点出队,记这个节点为poll,查看邻接表,若邻接表中有poll这个key,说明poll->list(...)
        这个list中的元素是依赖于poll的,也就是说poll是list中元素的直接父节点,
        而poll的祖先节点同时也是所有list元素的祖先节点,通通加入tmp对应的位置
    5.poll节点加入了tmp,list(num)的入度自然-1,当list(num)入度为0时,加入队列
    6.最后将tmp中的数据全部复制到res中返回
    */
    // 存储结果
    List<List<Integer>> res = new ArrayList<>();
    // 动态存储排序好的祖先节点
    List<Set<Integer>> tmp = new ArrayList<>();
    // 构造邻接表与入度数组
    // key->list(i)
    Map<Integer, List<Integer>> adj = new HashMap<>();
    int[] inDegree = new int[n];
    for(int[] edge : edges) {
        // 不存在则创建
        if(!adj.containsKey(edge[0])) {
            adj.put(edge[0], new ArrayList<>());
        }
        // 更新邻接表与入度数组 edge[0]->edge[1]
        adj.get(edge[0]).add(edge[1]);
        // edge[1]入度+1
        inDegree[edge[1]]++;
    }
    // 辅助队列
    Queue<Integer> que = new LinkedList<>();
    // 初始化队列
    for(int i = 0; i < n; i++) {
        // 入读为0直接入队
        if(inDegree[i] == 0) {
            // 入队了入度-1,避免后期重复入队
            inDegree[i]--;
            que.add(i);
        }
        // 每一个节点的位置占好
        res.add(new ArrayList<>());
        tmp.add(new TreeSet<>());
    }
    //开启循环
    while(!que.isEmpty()) {
        int size = que.size();
        for(int i = 0; i < size; i++) {
            // 弹出来的节点poll
            int poll = que.poll();
            // 若邻接表中有poll这个key,说明有poll->list(...)
            if(adj.containsKey(poll)) {
                // 遍历这个被poll指向的list集合
                for(int num : adj.get(poll)) {
                    // poll节点加入了tmp,list(num)的入度自然-1
                    inDegree[num]--;
                    // num节点的祖先节点包括poll+poll祖先节点
                    tmp.get(num).add(poll);
                    tmp.get(num).addAll(tmp.get(poll));
                    // 当list(num)入度为0时,加入队列
                    if(inDegree[num] == 0) {
                        que.add(num);
                    }
                }
            }
        }
    }
    // 最后将tmp的数据复制到res中[0,n-1]
    for(int i = 0; i < n; i++) {
        // addAll()是将另外一个集合的元素按顺序复制到res中
        res.get(i).addAll(tmp.get(i));
    }
    return res;
    }
}

cpp 解法, 执行用时: 184 ms, 内存消耗: 86.8 MB, 提交时间: 2023-10-26 23:52:14

class Solution {
    int n;
    vector<vector<int>> e, ans;

    void bfs(int S) {
        vector<bool> vis(n);
        queue<int> q;
        q.push(S); vis[S] = true;
        while (!q.empty()) {
            int sn = q.front(); q.pop();
            for (int fn : e[sn]) if (!vis[fn]) {
                vis[fn] = true;
                q.push(fn);
                ans[fn].push_back(S);
            }
        }
    }

public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        this->n = n;
        e = ans = vector<vector<int>>(n);
        for (auto &edge : edges) e[edge[0]].push_back(edge[1]);
        for (int i = 0; i < n; i++) bfs(i);
        for (int i = 0; i < n; i++) sort(ans[i].begin(), ans[i].end());
        return ans;
    }
};

cpp 解法, 执行用时: 460 ms, 内存消耗: 150.9 MB, 提交时间: 2023-10-26 23:51:37

class Solution {
public:
    vector<vector<int>> getAncestors(int n, vector<vector<int>>& edges) {
        vector<int> in(n, 0);
        vector<set<int>> ans(n);
        vector<vector<int>> son(n);
        queue<int> q;
        for(auto e : edges) {
            int from = e[0], to = e[1];
            in[to]++;   
            son[from].push_back(to);
        }
        for(int i = 0; i < n; i++) {
            if(in[i] == 0) q.push(i);
        }
        while(!q.empty()) {
            int now = q.front(); q.pop();
            for(auto next : son[now]) {
                ans[next].insert(now);
                for(auto f : ans[now]) {
                    ans[next].insert(f);
                }
                if(--in[next] == 0) q.push(next);
            }
        }
        vector<vector<int>> res(n);
        for(int i = 0; i < n; i++) {
            for(auto f : ans[i]) res[i].push_back(f);
        }
        return res;       
    }
};

java 解法, 执行用时: 179 ms, 内存消耗: 83.6 MB, 提交时间: 2023-10-26 23:51:17

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        //构建两个线性表，一个作为返回值，另一个使用`TreeSet`，可以在去重的同时进行元素的排序
        List<List<Integer>> ans = new ArrayList<>();
        List<Set<Integer>> demo = new ArrayList<>();

        //构建零阶矩阵(邻接表会更好)，以及入度数组
        int[] system = new int[n];
        int[][] grid = new int[n][n];

        //遍历`edges`，分别构建图中的边的关系以及各个节点的入度
        for (int[] edge : edges) {
            system[edge[1]]++;
            grid[edge[0]][edge[1]] = 1;
        }

        //将图中入度为0的节点入队列，同时“填充好”我们最初构建的两个线性表
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            if (system[i] == 0) {
                queue.offer(i);
                system[i]--;
            }
            ans.add(new ArrayList<>());
            demo.add(new TreeSet<>());
        }

        //分别对整个入度数组进行遍历，若入度为0，则加入队列，同时将该父节点以及该父节点的所有父节点加入线性表中
        while (!queue.isEmpty()) {
            int size = queue.size();

            while (size-- > 0) {
                int idx = queue.poll();
                for (int i = 0; i < n; i++) {
                    if (grid[idx][i] == 1) {
                        system[i]--;
                        demo.get(i).add(idx);
                        demo.get(i).addAll(demo.get(idx));
                    }
                    if (system[i] == 0) {
                        queue.offer(i);
                        system[i]--;
                    }
                }
            }
        }

        //将最终答案汇整到返回值`ans`中
        for (int i = 0; i < n; i++) {
            ans.get(i).addAll(demo.get(i));
        }

        return ans;
    }
}