重庆建设工程招投标信息网,seo薪资seo,为女人网上量体做衣网站,南昌专业网站排名推广文章目录1. 题目2. 解题1. 题目
总共有n个课程#xff0c;从0到n-1。 有些课程可能有先决条件#xff0c;例如#xff0c;你想修课程0#xff0c;你必须先修一门课程1#xff0c;这两门课之间的关系表示为:[0,1]
给定课程的总数和先决条件对的列表#xff0c;返回你可以…
文章目录1. 题目2. 解题1. 题目
总共有n个课程从0到n-1。 有些课程可能有先决条件例如你想修课程0你必须先修一门课程1这两门课之间的关系表示为:[0,1]
给定课程的总数和先决条件对的列表返回你可以得到所有课程的不同方法的数量。
n 10样例1
输入:
n 2
prerequisites [[1,0]]
输出: 1
说明:
你必须按照0-1的顺序上课。样例2
输入:
n 2
prerequisites []
Output: 2
输出:
你可以按0-1或1-0的顺序上课。https://tianchi.aliyun.com/oj/286601234951741590/302577566233072416
2. 解题
建图记录出入度n 比较小dfs 搜索
class Solution {
public:/*** param n: an integer, denote the number of courses* param p: a list of prerequisite pairs* return: return an integer,denote the number of topologicalsort*/int ans 0;int topologicalSortNumber(int n, vectorvectorint p) {// Write your code herevectorint indegree(n, 0);vectorbool vis(n, false);vectorvectorint g(n);for(auto pi : p){indegree[pi[0]];g[pi[1]].push_back(pi[0]);}dfs(g, vis, indegree, 0);return ans;}void dfs(vectorvectorint g, vectorbool vis, vectorint indegree, int count){if(count g.size()){ans;return;}for(int i 0; i g.size(); i){if(vis[i]) continue;if(indegree[i]0){vis[i] true;for(auto nt : g[i])indegree[nt]--;dfs(g, vis, indegree, count1);for(auto nt : g[i])indegree[nt];vis[i] false;}}}
};2490ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
