leetcode 210. Course Schedule II 拓扑排序 + HashSet

短命女 2022-06-08 09:16 131阅读 0赞

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: \[0,1\]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, \[\[1,0\]\]  
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is \[0,1\]

4, \[\[1,0\],\[2,0\],\[3,1\],\[3,2\]\]  
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is \[0,1,2,3\]. Another correct ordering is\[0,2,1,3\].

和上一道题题意完全一样，不过要打印一条可能的拓扑排序的结果，所以直接输出即可。

要和这一道题[leetcode 207. Course Schedule 课程调度 + 拓扑排序][leetcode 207. Course Schedule _ _] 和[leetcode 630. Course Schedule III 课程调度 + 贪心算法][leetcode 630. Course Schedule III _ _] 一起学习。

**需要注意的是，由于这道题更新了测试用例所以原先的代码可能出现问题，情况是这样的，记录后继结点要使用vector，不要使用set，因为假如存在(1,9)和(1,9)多次出现，这样就会出现问题，所以要使用vector**

代码如下：

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    import java.util.Set;
    
    /*
     * 本质就是判断图中是否有环
     * 拓扑排序的应用
     * http://blog.csdn.net/ljiabin/article/details/45846837
     * 和上面的一题完全一样，只是打印一下输出
     * */
    public class Solution 
    {
        public int[] findOrder(int numCourses, int[][] prerequisites)
        {       
            int []preCount=new int[numCourses];
            List<Set<Integer>> list=new ArrayList<Set<Integer>>();
            Arrays.fill(preCount, 0);
            for(int i=0;i<numCourses;i++)
                list.add(new HashSet<>());
    
            /*
             * list保存的是出度边，也即后继结点
             * 这里使用set是为了避免重复的边
             * perCount保存的说前驱节点的数量
             * */
            for(int i=0;i<prerequisites.length;i++)
            {
                int to=prerequisites[i][0];
                int from=prerequisites[i][1];
                list.get(from).add(to);
                preCount[to]++;
            }
    
            //使用队列来拓扑排序
            Queue<Integer> queue=new LinkedList<Integer>();
            for(int i=0;i<numCourses;i++)
            {
                if(preCount[i]==0)
                    queue.add(i);
            }
    
            List<Integer> resList=new ArrayList<>();
            while(queue.isEmpty()==false)
            {
                int from=queue.poll();
                resList.add(from);
    
                Set<Integer> one=list.get(from);
                Iterator<Integer> iter =one.iterator();
                while(iter.hasNext())
                {
                    int to=iter.next();
                    preCount[to]--;
                    if(preCount[to]==0)
                        queue.add(to);
                }
            }
    
            if(resList.size()==numCourses)
            {
                int []order=new int [numCourses];
                for(int i=0;i<numCourses;i++)
                    order[i]=resList.get(i);
                return order;
            }else
                return new int[0];
        }
    }

下面是C++的做法，和上一道题的做法一抹一眼，就是做一个拓扑排序

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution
    {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& reque)
        {
            vector<int> preCount(numCourses, 0);
            vector<vector<int>> next(numCourses, vector<int>());
            for (pair<int, int> key : reque)
            {
                int from = key.second;
                int to = key.first;
                next[from].push_back(to);
                preCount[to]++;
            }
    
            queue<int> que;
            for (int i = 0; i < preCount.size(); i++)
            {
                if (preCount[i] == 0)
                    que.push(i);
            }
    
            vector<int> res;
            while (que.empty() == false)
            {
                int from = que.front();
                que.pop();
                res.push_back(from);
                for (int i : next[from])
                {
                    preCount[i]--;
                    if (preCount[i] == 0)
                        que.push(i);
    
                }
            }
    
            if (res.size() != numCourses) 
                res.clear();
            return res;
        }
    };

[leetcode 207. Course Schedule _ _]: http://blog.csdn.net/jackzhang_123/article/details/78048156
[leetcode 630. Course Schedule III _ _]: http://blog.csdn.net/jackzhang_123/article/details/78850348