LeetCode 2924. Find Champion II
🔗 https://leetcode.com/problems/find-champion-ii
题目
- 给 n 个节点，代表 n 支参赛队伍，以及有向边 egeds，a ➡️ b，则代表 a 队比 b 队强
- 给出最后的冠军队伍，如果冠军不唯一，返回 -1
思路
- 一种是直接找到入度为 0 的节点，则是胜利队伍
- 另外一种麻烦且间接，每次找到出度为 0 的节点，代表这个节点必输，更新这个节点的边的节点，直到把所有边都更新完，剩下的节点便是冠军
代码
class Solution {
public:
int findChampion(int n, vector<vector<int>>& edges) {
vector<int> in(n);
int edge_num = edges.size();
for (auto& edge : edges) {
in[edge[1]]++;
}
unordered_set<int> s;
int count = 0;
int ans = -1;
for (int i = 0; i < n; i++) {
if (in[i] == 0) {
count++;
ans = i;
}
}
if (count != 1) return -1;
return ans;
}
};2924