Сегодня мы решаем задачу 2924. Find Champion II
🏆 Задача:
В турнире n команд представлены как вершины DAG (ориентированного ацикличного графа). Если команда a сильнее команды b, это отображается направленным ребром от a к b. Требуется найти чемпиона турнира — вершину, из которой достижимы все остальные вершины. Если чемпиона нет или их несколько, вернуть −1.
😊 Идея:
В DAG вершина с отсутствующими входящими рёбрами (in_degree = 0) является источником. Если в графе ровно один источник, он становится кандидатом в чемпионы, так как из него достижимы все остальные вершины
(Нетривиальный момент: это утверждение не верно в общем случе, но в случае DAG его несложно доказать).
Если источников больше или ни одного, чемпиона не существует.
Сложность
-
🕒 Временная сложность:
O(m): Обход рёбер для подсчёта входящих рёбер.O(n): Проход по массиву in_degree.- Итого:
O(n+m).
-
🗂️ Пространственная сложность:
O(n): Для хранения массива in_degree.
Исходный код решения
impl Solution {
pub fn find_champion(n: i32, edges: Vec<Vec<i32>>) -> i32 {
let mut in_degree = vec![0; n as usize];
// Calculate in-degrees for each node
for e in &edges {
in_degree[e[1] as usize] += 1;
}
// Identify the potential champion
let mut champion = -1;
let mut n_champions = 0;
for (node, °ree) in in_degree.iter().enumerate() {
if degree == 0 {
champion = node as i32;
n_champions += 1;
}
}
// There must be exactly one node with in-degree 0
if n_champions == 1 {
champion
} else {
-1
}
}
}