thảo luận Leetcode mỗi ngày

impl Solution {
    pub fn get_ancestors(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let un = n as usize;
        let list_edge =
            edges.into_iter().
                fold(vec![vec![]; un], |mut acc, edge| {
                    acc[edge[0] as usize].push(edge[1] as usize);
                    acc
                });

        let mut visited = vec![false; un];
        let mut ancestor_lists = vec![vec![]; un];

        fn dfs(source: i32, vertex: usize, list_edge: &Vec<Vec<usize>>, visited: &mut Vec<bool>, ancestor_lists: &mut Vec<Vec<i32>>) {
            visited[vertex] = true;

            for &neighbour in &list_edge[vertex] {
                if visited[neighbour] {
                    continue;
                }

                ancestor_lists[neighbour].push(source);

                dfs(source, neighbour, list_edge, visited, ancestor_lists);
            }
        };

        for source in 0..n {
            visited.iter_mut().for_each(|cell| *cell = false);

            dfs(source, source as usize, &list_edge, &mut visited, &mut ancestor_lists);
        }

        ancestor_lists
    }
}

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        graph = defaultdict(list)
        for edge in edges:
            graph[edge[1]].append(edge[0])

        ans = defaultdict(set)
        def dfs(vertex):
            if vertex in ans:
                return ans[vertex]

            ancestors = set()
            for neighbor in graph[vertex]:
                ancestors.add(neighbor)
                ancestors.update(dfs(neighbor))

            ans[vertex] = ancestors
            return ancestors


        results = []
        for i in range(n):
            results.append(sorted(dfs(i)))

        return results

class Solution {

    /**
     * @param Integer $n
     * @param Integer[][] $edges
     * @return Integer[][]
     */
    function getAncestors($n, $edges) {
        $dict = []; // create hash table to check parents of nodes
        foreach ($edges as $ed) {
            $dict[$ed[1]][$ed[0]] = $ed[0];
        }

        // find ancestors
        $ancestors = [];
        for ($i=0; $i<$n; $i++) {
            $parents = [];
            $this->getParents($dict, $i, $parents);
            sort($parents); // sort to fit with expects result
            $ancestors[] = $parents;
        }

        return $ancestors;
    }

    /**
     * @param Integer[][] $dict
     * @param Integer $node
     * @param Integer[] $parent
     */
    function getParents($dict, $node, &$parents = []) {
        if (!isset($dict[$node])) return;

        foreach ($dict[$node] as $p) {
            // don't need to check if the parent is already in the list
            if (isset($parents[$p])) continue;

            $parents[$p] = $p;
            $this->getParents($dict, $p, $parents);
        }
    }
}

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        rGraph = defaultdict(list)
        for u, v in edges:
            rGraph[v].append(u)
        
        @cache
        def dp(src):
            ans = set(rGraph[src])
            for ancestor in rGraph[src]:
                ans |= dp(ancestor)
            return ans
        
        ans = []
        for u in range(n):
            ans.append(sorted(dp(u)))
        return ans

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<Integer>[] adjacents = new ArrayList[n];
        List<Integer>[] ancestors = new ArrayList[n];
        List<List<Integer>> res = new ArrayList<>();
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            adjacents[i] = new ArrayList<>();
            ancestors[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adjacents[edge[1]].add(edge[0]);
        }
        for(int i= 0 ; i < n ;i++){
            dfs(i, adjacents,visited,ancestors);
            Collections.sort(ancestors[i]);
            res.add(ancestors[i]);
        }
        return res;

    }
    public List<Integer> dfs(int node, List<Integer>[] adjacents, boolean[] visited, List<Integer>[] ancestors) {
        if (visited[node] == true) {
            return ancestors[node];
        }
        Set<Integer> ancestor = new HashSet();
        for (int adjacent : adjacents[node]) {
            ancestor.add(adjacent);
            ancestor.addAll(dfs(adjacent, adjacents, visited,ancestors));
        }
        visited[node] = true;
        ancestors[node] = new ArrayList<>(ancestor);
        return ancestors[node];
    }
}

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        graph = defaultdict(list)

        for [s , r] in edges:
            graph[r].append(s)
       
        self.vis = n * [False]
        memo = {}
        def dfs(root):
            if root in memo: return memo[root]
            if len(graph[root]) == 0:
                memo[root] = []
                return []

            self.vis[root] = True
            ancestors = set()

            for e in graph[root]:
                if self.vis[e]: continue
                ancestors.add(e)
                ancestors.update(dfs(e))
           
            self.vis[root] = False
            result = sorted(ancestors)
            memo[root] = result

            return result            

        res = []
        for i in range(n):
            res.append(dfs(i))

        return res

class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        reversed_adj = [[] for _ in range(n)]

        for edge in edges:
            [u, v] = edge
            reversed_adj[v].append(u)
        
        ancestors = [set() for _ in range(n)]
        visited = set()

        def get_ancestors(u):
            if u in visited:
                return ancestors[u]
            visited.add(u)
            for v in reversed_adj[u]:
                ancestors[u].add(v)
                ancestors[u].update(get_ancestors(v))
            return ancestors[u]
        
        return [
            sorted(get_ancestors(u))
            for u in range(n)
        ]

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<Set<Integer>> g = initializeListOfSets(n);
        List<Set<Integer>> ancestors = initializeListOfSets(n);
        boolean[] processed = new boolean[n];

        Arrays.stream(edges).forEach(edge -> g.get(edge[1]).add(edge[0]));
        IntStream.range(0, n).forEach(vertex -> {findAncestors(vertex, g, ancestors, processed);});

        return ancestors.stream()
                        .map(set -> set.stream().sorted().collect(Collectors.toList()))
                        .collect(Collectors.toList());
    }
    private void findAncestors(int vertex, List<Set<Integer>> g,
                                List<Set<Integer>> ancestors, boolean[] processed) {
        if (processed[vertex]) return;

        g.get(vertex).forEach(neighbor -> {
            findAncestors(neighbor, g, ancestors, processed);
            ancestors.get(vertex).add(neighbor);
            ancestors.get(vertex).addAll(ancestors.get(neighbor));
        });

        processed[vertex] = true;
    }
    private List<Set<Integer>> initializeListOfSets(int n) {
        return IntStream.range(0, n)
                        .mapToObj(i -> new HashSet<Integer>())
                        .collect(Collectors.toList());
    }
}

// Defines the signature for the `cook`-function,
// although this is not strictly necessary
// thanks to the powerful type-inference system in F#
type Cook = string list -> string list list -> string list -> string list

let rec cook: Cook =
    fun recipes ingredientSets supplies ->
        let recipes = List.zip recipes ingredientSets
        let canCook = List.except supplies >> List.isEmpty
        let completed, pending = recipes |> List.partition (snd >> canCook)

        match completed with
        | [] -> []
        | completed ->
            let completed = completed |> List.map fst

            match pending with
            | [] -> completed
            | pending ->
                let newRecipes, newIngredients = pending |> List.unzip
                let newSupplies = completed |> List.append supplies

                cook newRecipes newIngredients newSupplies |> List.append completed

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> result = new ArrayList<>();
        ArrayList<List<Integer>> adjacent = new ArrayList<>();
        int index = 0;
        boolean[] visited = new boolean[n];
        for(int i =0;i<n;i++){
            adjacent.add(new ArrayList<>());
            result.add(new ArrayList<>());
        }

        for(int[] edge: edges){
            adjacent.get(edge[1]).add(edge[0]);
        }

        for(List<Integer> list: adjacent){
            SortedSet<Integer> set = new TreeSet<>();
            for(int v:list){
                if(!visited[v])
                    topoSort(v,visited,adjacent,result);
                set.add(v);
                set.addAll(result.get(v));             
            }
            visited[index] = true;
            if(result.get(index).size()==0) {
                result.get(index).addAll(set);
            } 
            index++;
        }
        return result;
    }
    
    public void topoSort(int v, boolean[] visited,ArrayList<List<Integer>> adjacent, List<List<Integer>> result ){
        SortedSet<Integer> set = new TreeSet<>();       
        for(int vertex:adjacent.get(v)){
            if(!visited[vertex])
                topoSort(vertex,visited,adjacent,result);
            set.add(vertex);
            set.addAll(result.get(vertex));             
        }
        visited[v] = true;
        result.get(v).addAll(set);
    }
}

public class Solution
{
    public IList<IList<int>> GetAncestors(int n, int[][] edges)
    {
        Vertex[] graph = new Vertex[n];
        IList<IList<int>> result = new IList<int>[n];
        for (int i = 0; i < n; i++)
        {
            graph[i] = new(i);
            result[i] = new List<int>();
        }
        for (int i = 0; i < edges.Length; i++)
        {
            int u = edges[i][0];
            int v= edges[i][1];
            graph[u].neighbors.Add(v);
        }
        
        List<int>[] ancestors = new List<int>[n];
        for (int i = 0; i < n; i++)
        {
            List<int> path = new();
            DFS(graph[i], path, graph, new());
            ancestors[i] = path;
        }

        for (int i = 0; i < ancestors.Length; i++)
        {
            List<int> children = ancestors[i];
            for (int j = 0; j < children.Count; j++)
            {
                int child = children[j];
                if (child == i)
                {
                    continue;
                }
                result[child].Add(i);
            }
        }

        return result;
    }

    private void DFS(Vertex vertex, List<int> path, Vertex[] graph, HashSet<int> visited)
    {
        if (visited.Contains(vertex.id))
        {
            return;
        }

        visited.Add(vertex.id);
        foreach (var neighbor in vertex.neighbors)
        {
            DFS(graph[neighbor], path, graph, visited);
        }
        path.Add(vertex.id);
    }

    public class Vertex
    {
        public int id;
        public List<int> neighbors = new();

        public Vertex(int id)
        {
            this.id = id;
        }
    }
}

impl Solution {
    pub fn get_ancestors(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        use std::collections::{HashMap, HashSet};
        let n = n as usize;
        let mut ancestors = HashMap::<usize, HashSet<usize>>::new();
        let graph = {
            let mut graph = vec![HashSet::<usize>::new(); n + 1];
            for edge in edges {
                graph[edge[1] as usize].insert(edge[0] as usize);
            }
            graph[n] = (0..n).collect();
            graph
        };

        fn ancestors_of(
            i: usize,
            acs: &mut HashMap<usize, HashSet<usize>>,
            graph: &[HashSet<usize>],
        ) {
            if acs.contains_key(&i) {
                return;
            }

            acs.insert(i, graph[i].clone());
            for &j in &graph[i] {
                ancestors_of(j, acs, graph);
                acs.insert(i, HashSet::union(&acs[&i], &acs[&j]).copied().collect());
            }
        }
        ancestors_of(n, &mut ancestors, &graph);
        (0..n).into_iter().map(|i| {
            let s = &ancestors[&i];
            let mut v: Vec<_> = s.iter().map(|i| *i as i32).collect();
            v.sort_unstable();
            v
        }).collect()
    }
}