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

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()
    }
}

class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        Map<Integer, List<Integer>> graph = buildReverseGraph(edges);
        List<List<Integer>> ancestors = new ArrayList<>();
        for (int i  = 0; i < n; i++) {
            boolean[] isVisited = new boolean[n];
            List<Integer> ancestor = new ArrayList<>();
            dfs(i, graph, isVisited);
            for (int node = 0; node < n; node++) {
                if (isVisited[node] == true) {
                    ancestor.add(node);
                }
            }
            ancestors.add(ancestor);
        }
        return ancestors;
    }

    public Map<Integer, List<Integer>> buildReverseGraph(int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            var adjVertexs = graph.getOrDefault(edge[1], new ArrayList<>());
            adjVertexs.add(edge[0]);
            graph.put(edge[1], adjVertexs);
        }
        return graph;
    }

    public void dfs(int vertex, Map<Integer, List<Integer>> graph, boolean[] isVisited) {
        for (int nextVertex : graph.getOrDefault(vertex, new ArrayList<>())) {
            if (!isVisited[nextVertex]) {
                isVisited[nextVertex] = true;
                dfs(nextVertex, graph, isVisited);
            }
        }
    }

impl Solution {
    pub fn get_ancestors(n: i32, edges: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        use std::collections::HashSet;
        let n = n as usize;
        let mut ancestors_: Vec<Option<HashSet<usize>>> = vec![None; n + 1];
        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 Vec<Option<HashSet<usize>>>, graph: &[HashSet<usize>]) {
            if acs[i].is_some() {
                return;
            }

            let mut acs_i = graph[i].clone();
            for &j in graph[i].iter() {
                ancestors_of(j, acs, graph);
                if let Some(ref acs_j) = acs[j] {
                    acs_i = HashSet::union(&acs_i, &acs_j).copied().collect();   
                }
            }
            acs[i] = Some(acs_i);
        }
        ancestors_of(n, &mut ancestors_, &graph);
        ancestors_.pop();
        ancestors_.into_iter().map(|s| {
            let mut v: Vec<_> = unsafe { s.unwrap_unchecked() }.into_iter().map(|i| i as i32).collect();
            v.sort_unstable();
            v
        }).collect()
    }
}

var getAncestors = function(n, edges) {
    const graph = {};
    for (const [from, to] of edges) {
        if (from in graph === false)
            graph[from] = [];
        graph[from].push(to);
    }

    const dfs = (node, parent) => {
        if (node in graph === false) return;
        for (const neighbor of graph[node]) {
            if (res[neighbor].has(parent)) continue;
            res[neighbor].add(parent);
            dfs(neighbor, parent);
        }
    }

    const res = Array.from({ length: n }, () => new Set());

    for (let i = 0; i < n; i++) {
        dfs(i, i);
    }

    return res.map(x => [...x].sort((a, b) => a - b));
};

class Solution {
    public List<String> findAllRecipes(String[] recipes, List<List<String>> ingredients, String[] supplies) {
        Map<String, Boolean> hasSupplies = new HashMap<>();
        for (String supply : supplies) {
            hasSupplies.put(supply, true);
        }
        Map<String, List<String>> ingredientTree = buildIngredientTree(recipes, ingredients);

        List<String> canMake = new ArrayList<>();
        for (String recipe : recipes) {
            if (canCreateThis(recipe, ingredientTree, hasSupplies, new HashMap<>())) {
                canMake.add(recipe);
            }
        }

        return canMake;
    }

    public Map<String, List<String>> buildIngredientTree(String[] recipes, List<List<String>> ingredients) {
        Map<String, List<String>> ingredientTree = new HashMap<>();

        for (int i = 0; i < recipes.length; i++) {
            for (String ingredient : ingredients.get(i)) {
                List<String> require = ingredientTree.getOrDefault(recipes[i], new ArrayList<>());
                require.add(ingredient);
                ingredientTree.put(recipes[i], require);
            }
        }

        return ingredientTree;
    }

    public boolean canCreateThis(String recipe, Map<String, List<String>> ingredientTree, Map<String, Boolean> hasSupplies, Map<String, Boolean> isVisited) {
        if (hasSupplies.get(recipe) != null) {
            return hasSupplies.get(recipe);
        }

        if (null != isVisited.get(recipe)) {
            return false;
        }

        boolean canCreate = (ingredientTree.get(recipe) != null);
        for (String ingredient : ingredientTree.getOrDefault(recipe, new ArrayList<>())) {
            if (null == isVisited.get(ingredient)) {
                isVisited.put(ingredient, true);
                canCreate &= canCreateThis(ingredient, ingredientTree, hasSupplies, isVisited);
            }
        }

        hasSupplies.put(recipe, canCreate);
        return canCreate;
    }
}