leetcode

Leetcode problem solutions
git clone https://git.sinitax.com/sinitax/leetcode
Log | Files | Refs | sfeed.txt

2924-find-champion-ii.rs (2984B)

      1/// 2924. Find Champion II (Medium)
      2///
      3/// There are n teams numbered from 0 to n - 1 in a tournament; each team is
      4/// also a node in a *DAG*.
      5///
      6/// You are given the integer n and a *0-indexed* 2D integer array edges of
      7/// length m representing the *DAG*, where edges[i] = [ui, vi] indicates that
      8/// there is a directed edge from team ui to team vi in the graph.
      9///
     10/// A directed edge from a to b in the graph means that team a is *stronger*
     11/// than team b and team b is *weaker* than team a.
     12///
     13/// Team a will be the *champion* of the tournament if there is no team b that
     14/// is *stronger* than team a.
     15///
     16/// Return the team that will be the *champion* of the tournament if there is a
     17/// *unique* champion, otherwise, return -1.
     18///
     19/// *Notes*
     20///
     21///   * A *cycle* is a series of nodes a1, a2, ..., an, an+1 such that node a1 is
     22///   the same node as node an+1, the nodes a1, a2, ..., an are distinct, and
     23///   there is a directed edge from the node ai to node ai+1 for every i in the
     24///   range [1, n].
     25///   * A *DAG* is a directed graph that does not have any *cycle*.
     26///
     27/// *Example 1:*
     28///
     29///   *Input:* n = 3, edges = [[0,1],[1,2]]
     30///   *Output:* 0
     31///   *Explanation: *Team 1 is weaker than team 0. Team 2 is weaker than team 1.
     32///   So the champion is team 0.
     33///
     34/// *Example 2:*
     35///
     36///   *Input:* n = 4, edges = [[0,2],[1,3],[1,2]]
     37///   *Output:* -1
     38///   *Explanation:* Team 2 is weaker than team 0 and team 1. Team 3 is weaker
     39///   than team 1. But team 1 and team 0 are not weaker than any other teams. So
     40///   the answer is -1.
     41///
     42/// *Constraints:*
     43///
     44///   * 1 <= n <= 100
     45///   * m == edges.length
     46///   * 0 <= m <= n * (n - 1) / 2
     47///   * edges[i].length == 2
     48///   * 0 <= edge[i][j] <= n - 1
     49///   * edges[i][0] != edges[i][1]
     50///   * The input is generated such that if team a is stronger than team b, team b
     51///   is not stronger than team a.
     52///   * The input is generated such that if team a is stronger than team b and
     53///   team b is stronger than team c, then team a is stronger than team c.
     54///
     55use leetcode::*;
     56
     57struct Solution {}
     58
     59impl Solution {
     60    pub fn find_champion(n: i32, edges: Vec<Vec<i32>>) -> i32 {
     61        let mut stronger = [0usize; 101];
     62        for edge in edges {
     63            stronger[edge[1] as usize] += 1;
     64        }
     65        let mut strongest = -1;
     66        for i in 0..n {
     67            if stronger[i as usize] == 0 {
     68                if strongest >= 0 {
     69                    return -1;
     70                }
     71                strongest = i;
     72            }
     73        }
     74        strongest
     75    }
     76}
     77
     78pub fn main() {
     79    println!("{}", Solution::find_champion(arg_into(1), arg_into(2)));
     80}
     81
     82#[cfg(test)]
     83mod tests {
     84    use crate::Solution;
     85    use leetcode::vvi;
     86
     87    #[test]
     88    fn test() {
     89        assert_eq!(Solution::find_champion(3, vvi("[[0,1],[1,2]]")), 0);
     90        assert_eq!(Solution::find_champion(4, vvi("[[0,2],[1,3],[1,2]]")), -1);
     91        assert_eq!(Solution::find_champion(2, vvi("[[1,0]]")), 1);
     92    }
     93}