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

class Solution:
    def maximumImportance(self, n: int, roads: List[List[int]]) -> int:
        d = defaultdict(int)
        w = [0] * n

        for road in roads:
            [u, v] = road
            d[u] += 1
            d[v] += 1
        
        sorted_d = sorted([(v, i) for i, v in d.items()], reverse=True)

        for j, e in enumerate(sorted_d):
            (v, i) = e
            w[i] = n - j

        ans = 0
        for road in roads:
            [u, v] = road
            ans += (w[u] + w[v])
        return ans

public class Solution
{
    public long MaximumImportance(int n, int[][] roads)
    {
        int[] cities = new int[n];
        for (int i = 0; i < roads.Length; i++)
        {
            int u = roads[i][0];
            int v = roads[i][1];
            cities[u]++;
            cities[v]++;
        }

        Array.Sort(cities);
        long result = 0;
        while (n > 0)
        {
            result += cities[n - 1] * (long)n;
            n--;
        }

        return result;
    }
}

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