leetcode2924--找到冠军II

1. 题意

给定一个有向无环图，方向表示胜负关系；求最后胜出的人。

2. 题解

将所有人标记为胜者，统计出度去掉对应胜者标记；

最后统计胜者数目，是否大于1，若大于1，则没有胜者，否则返回那个胜者。

2.1 我的代码

class Solution {
public:void dfs(int r, const vector<vector<int>> &g, vector<int> &ch, vector<int> &vis) {int n = ch.size();for (int i = 0;i < n; ++i) {if (!vis[i] && g[r][i]) {vis[i] = 1;ch[i] = 0;dfs(i, g, ch, vis);}}}int findChampion(int n, vector<vector<int>>& edges) {vector<vector<int>> g(n ,vector<int>(n, 0));vector<int> vis(n, 0);vector<int> ch(n, 1);for(auto &edge:edges) {g[edge[0]][edge[1]] = 1;ch[edge[1]] = 0;}for (int i = 0; i < n; ++i) {if ( !vis[i] ) {vis[i] = 1;dfs(i, g, ch, vis);}}int ch_num = count(ch.begin(), ch.end(), 1);if ( ch_num != 1)return -1;return find(ch.begin(), ch.end(), 1) - ch.begin();}
};

2.2 更清晰的代码

  int findChampion(int n, vector<vector<int>>& edges) {vector<int> inDeg(n, 0);for (auto &edge: edges) {inDeg[edge[1]]++;}int champion = -1;for (int i = 0;i < n; ++i) {if (inDeg[i] == 0) {if (champion == -1)champion = i;elsereturn -1;}}return champion;}