巴中市建设局网站,恩施做网站多少钱,网站建设与管理的书,网易官网建立个人网站1. 题意
给定一个有向无环图#xff0c;方向表示胜负关系#xff1b;求最后胜出的人。
2. 题解
将所有人标记为胜者#xff0c;统计出度去掉对应胜者标记#xff1b;
最后统计胜者数目#xff0c;是否大于1#xff0c;若大于1#xff0c;则没有胜者#xff0c;否则…1. 题意
给定一个有向无环图方向表示胜负关系求最后胜出的人。
2. 题解
将所有人标记为胜者统计出度去掉对应胜者标记
最后统计胜者数目是否大于1若大于1则没有胜者否则返回那个胜者。
2.1 我的代码
class Solution {
public:void dfs(int r, const vectorvectorint g, vectorint ch, vectorint 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, vectorvectorint edges) {vectorvectorint g(n ,vectorint(n, 0));vectorint vis(n, 0);vectorint 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, vectorvectorint edges) {vectorint 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;}
