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

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        vertex = set([i for i in range(n)])
        for _, v in edges:
            vertex.discard(v)
        
        return vertex.pop() if len(vertex) == 1 else -1

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        return -1 if n - len(set([i for _, i in edges])) != 1 else n*(n - 1)//2 - sum(list(set([i for _, i in edges])))

class Solution {
    fun findChampion(n: Int, edges: Array<IntArray>): Int {
        val notChampion = BooleanArray(n)
        edges.forEach { (_, v) -> notChampion[v] = true }
        
        var champion = -1
        for (i in 0 until n) {
            if (!notChampion[i]) {
                if (champion != -1) return -1
                champion = i
            }
        }
        return champion
    }
}

func findChampion(n int, edges [][]int) int {
    arr := make([]int, n)

    for _, row := range edges {
        arr[row[1]]--
    }

    champ := -1
    countChamp := 0

    for i := range arr {
        if arr[i] == 0 {
            champ = i
            countChamp++
        }
    }

    if countChamp > 1 {
        return -1
    }

    return champ
}

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        loser = set(edge[1] for edge in edges)
        winner = [i for i in range(n) if i not in loser]
        return winner[0] if len(winner) == 1 else -1

public class Solution {
    public void dfs(int u, int n, int[][] edges, IList<int> stronger)
    {
        for(int i = 0; i<edges.Length; i++)
        {
            if(edges[i][0] == u && !stronger.Contains(edges[i][1]))
            {
                stronger.Add(edges[i][1]);
                dfs(edges[i][1], n, edges, stronger);
            }
        }
    }
    public int FindChampion(int n, int[][] edges) {
        List<int> list = Enumerable.Range(0, n).ToList();
        for(int i = 0; i<n; i++)
        {
            List<int> stronger = new List<int>{i};
            dfs(i, n, edges, stronger);
            if(list.All(i => stronger.Contains(i)))
                return i;
        }
        return -1;
    }
}

class Solution {
    public int findChampion(int n, int[][] edges) {
        List<Integer> list = new ArrayList();
        int[] inDegree = new int[n];
        for(int[] edge: edges)
            inDegree[edge[1]]++;
        for(int i= 0;i<n;i++)
            if (inDegree[i]==0)
                list.add(i);
        return list.size()==1?list.get(0):-1;
    }
}

function shortestDistanceAfterQueries(n: number, queries: number[][]): number[] {
    const g: Map<number, number[]> = new Map();
    for (let i = 0; i < n - 1; i++) {
        if (!g.has(i)) {
            g.set(i, []);
        }
        g.get(i)?.push(i + 1);
    }

    const bfs = () => {
        const arr: number[] = Array(n).fill(-1);
        arr[0] = 0;
        const q: number[] = [0];

        let idx = 0;
        while (idx < q.length) {
            const node = q[idx++];
            if (g.has(node)) {
                for (const nei of g.get(node)!) {
                    if (arr[nei] === -1) {
                        arr[nei] = arr[node] + 1;
                        q.push(nei);
                    }
                }
            }
        }
        return arr[n - 1];
    }
    const res: number[] = [];
    for (const [u, v] of queries) {
        if (!g.has(u)) {
            g.set(u, []);
        }
        g.get(u)?.push(v);
        res.push(bfs());
    }

    return res;
};

class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n - 1; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(i + 1);

            graph.add(list);
        }
        graph.add(new ArrayList<Integer>());

        int m = queries.length;
        int[] res = new int[m];
        for (int i = 0; i < m; i++) {
            int u = queries[i][0];
            int v = queries[i][1];
            graph.get(u).add(v);
            int path = bfs(n, graph);
            res[i] = path;
        }

        return res;
    }

    public int bfs(int n, List<List<Integer>> graph) {
        int m = graph.size();
        int[] visited = new int[n];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] { 0, 0 });
        visited[0] = 1;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int node = current[0];
            int distance = current[1];

            if (node == m - 1) {
                return distance;
            }

            for (int neighbor : graph.get(node)) {
                if (visited[neighbor] == 0) {
                    visited[neighbor] = 1;
                    queue.add(new int[] { neighbor, distance + 1 });
                }
            }
        }
        return -1;
    }
}

const bfs = (adjList, n) => {
    const queue = [0];
    const visited = new Set();
    visited.add(0);
    let step = 0;
    while(queue.length > 0){
        const levelSize = queue.length;
        for(let i = 0; i < levelSize; i++){
            const node = queue.shift();
            if(node === n - 1) return step;
            for(const adjNode of adjList.get(node)){
                if(visited.has(adjNode)) continue;
                queue.push(adjNode);
                visited.add(adjNode);
            }
        }
        step++;
    }
}

var shortestDistanceAfterQueries = function(n, queries) {
    const adjList = new Map();
    const result = [];
    for(let i = 0; i < n - 1; i++){
        adjList.set(i, [i + 1]);
    }
    for(const [from, to] of queries){
        adjList.get(from).push(to);
        result.push(bfs(adjList, n));
    }
    return result;
};

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        adj = defaultdict(list)
        for i in range(n - 1):
            adj[i].append(i+1)
        
        def bfs():
            q, visited, count = deque([0]), [False for _ in range(n)], 0
            visited[0] = True
            while q:
                m = len(q)
                for _ in range(m):
                    u = q.popleft()
                    if u == n - 1:
                        return count
                    for v in adj[u]:
                        if not visited[v]:
                            q.append(v)
                            visited[v] = True
                count += 1

        result = []
        minShortest = n - 1
        for u, v in queries:
            if minShortest == 1:
                result.append(1)
                continue
            adj[u].append(v)
            currShortest = bfs()
            minShortest = min(minShortest, currShortest)
            result.append(minShortest)
        return result

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        adj = defaultdict(list)
        for i in range(n - 1):
            adj[i].append(i + 1)
        res = []

        def bfs():
            q = deque([0])
            level = 0
            visited = set()
            while q:
                l = len(q)
                for _ in range(l):
                    node = q.popleft()
                    if node == n - 1:
                        return level
                    for nei in adj[node]:
                        if nei not in visited:
                            q.append(nei)
                            visited.add(nei)
                level += 1
            return level

        for s, d in queries:
            if res and res[-1] == 1:
                res.append(1)
                continue
            adj[s].append(d)
            res.append(bfs())
        return res