笔试题8 -- 利用拓扑排序解决体育课测验

本文主要是介绍笔试题8 -- 利用拓扑排序解决体育课测验，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

笔试题8 – 利用拓扑排序解决体育课测验

原题重现

题目链接：体育课测验(二)_牛客 (nowcoder.com)

体育课共有 numProject 个考核项目，编号为 0 到 numProject−1。考核中每两个项目被划分为一组得到分组数组 groups[i]，现规定若想完成项目 groups[i] [0]，必须先完成 groups[i] [1]。保证所有分组互不相同，若分组情况能顺利完成考核，请返回任意的一个完成顺序，否则返回空数组。

数据范围：

1 ≤ numProject ≤ 2000
1 ≤ groups[i].length ≤ numProject * (numProject−1)

在这里插入图片描述

解题思路

通过题目描述 “若想完成项目 groups[i] [0]，必须先完成 groups[i] [1]” ，这说明同组的两项目之间存在先后顺序，且每组内刚好有两个项目，他们之间的先后关系可以用箭头来表示 groups[i] [0] <- groups[i] [1] ，所以联想到利用拓扑排序可以有效解决该问题。

示例代码

本代码利用Kahn算法实现拓扑排序

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numProject int整型 * @param groups int整型vector<vector<>> * @return int整型vector*/vector<int> findOrder(int numProject, vector<vector<int> >& groups) {vector<vector<int>> edges(numProject);  // 存储边vector<int> in(numProject);  // 存储入度// 1.建图for(auto pair: groups){// pair[0] <- pair[1]edges[pair[1]].push_back(pair[0]);in[pair[0]]++;}// 2.入度为0的点，加入到队列中queue<int> q;for(int i = 0; i < numProject; i++){if(in[i] == 0) { q.push(i); }}// 3.拓扑排序（层序遍历）vector<int> ret;while(!q.empty()){auto a = q.front();q.pop();// 塞入结果数组ret.push_back(a);// 移除该点相关信息// a -> bfor(auto b: edges[a]){if(--in[b] == 0)  // 已经入度为0的点就可以利用队列准备放入结果数组{q.push(b);}}}// 4.返回if(ret.size() == numProject) { return ret; }return {};}
};