鱼C论坛

 找回密码
 立即注册
查看: 1630|回复: 4

[技术交流] C++刷leetcode(207. 课程表)【拓扑排序】

[复制链接]
发表于 2020-4-9 20:25:33 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 糖逗 于 2020-5-8 17:35 编辑

题目描述:
  1. 你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。

  2. 在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]

  3. 给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?

  4.  

  5. 示例 1:

  6. 输入: 2, [[1,0]]
  7. 输出: true
  8. 解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。
  9. 示例 2:

  10. 输入: 2, [[1,0],[0,1]]
  11. 输出: false
  12. 解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。
  13.  

  14. 提示:

  15. 输入的先决条件是由 边缘列表 表示的图形,而不是 邻接矩阵 。详情请参见图的表示法。
  16. 你可以假定输入的先决条件中没有重复的边。
  17. 1 <=&#160;numCourses <= 10^5

  18. 来源:力扣(LeetCode)
  19. 链接:https://leetcode-cn.com/problems/course-schedule
  20. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码



  1. #include <vector>
  2. #include <iostream>
  3. #include <queue>
  4. using namespace std;



  5. bool solution(int number, vector<vector<int> > &input){
  6.     vector<int> indegree(number, 0);
  7.         vector<vector<int> > graph(number);
  8.         //初始化图和进度
  9.         for(int i = 0; i < input.size(); i++){
  10.                 indegree[input[i][0]] ++;
  11.                 graph[input[i][1]].push_back(input[i][0]);
  12.         }
  13.        
  14.         queue<int> temp;
  15.         for(int i = 0; i < number; i++){
  16.                 if(indegree[i] == 0) temp.push(i);
  17.         }
  18.        
  19.         int count = 0;
  20.        
  21.         while(!temp.empty()){
  22.                 int temp2 = temp.front();
  23.                 temp.pop();
  24.                 count ++;
  25.                 for(int i = 0 ; i < graph[temp2].size(); i++){
  26.                         indegree[graph[temp2][i]]--;
  27.                         if(indegree[graph[temp2][i]]== 0){
  28.                                 temp.push(graph[temp2][i]);
  29.                         }
  30.                 }
  31.                
  32.         }
  33.         return  count == number;
  34.        
  35. }




  36. int main(void){
  37.         cout << "send number for the total courses" << endl;
  38.         int number;
  39.         cin >> number;
  40.         cin.clear();
  41.         cout << "send row for the vector" << endl;
  42.         int row;
  43.         cin >> row;
  44.         cin.clear();
  45.         vector<vector<int> > input(row);
  46.         cout << "send the number for the vector" << endl;
  47.         int numbers;
  48.         for(int i = 0 ; i < row; i++){
  49.                 for(int j = 0; j < 2; j++){
  50.                         cin >> numbers;
  51.                         input[i].push_back(numbers);
  52.                 }
  53.         }
  54.        
  55.         bool res = solution(number, input);
  56.         cout << res << endl;
  57.         return 0;
  58. }
复制代码



注意事项:
1.这里用到拓扑排序。
2.graph中的对应关系如图1。

图1

图1

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2020-4-9 21:56:24 | 显示全部楼层
不得不说图画的有点丑。。。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-9 21:57:19 | 显示全部楼层
乘号 发表于 2020-4-9 21:56
不得不说图画的有点丑。。。

灵魂画手
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-9 21:59:49 | 显示全部楼层

    --------
    |        |
    |       /|
    |      / |
     \      /
       \  /

这是你的灵魂画笔
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-9 22:00:27 | 显示全部楼层
乘号 发表于 2020-4-9 21:59
--------
    |        |
    |       /|

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-2 10:20

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表