🔗 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
)
)
