lintcode615. 课程表拓扑排序

拼搏现实的明天。 2023-07-06 11:41 22阅读 0赞

现在你总共有 n 门课需要选，记为 0 到 n - 1.  
一些课程在修之前需要先修另外的一些课程，比如要学习课程 0 你需要先学习课程 1 ，表示为\[0,1\]  
给定n门课以及他们的先决条件，判断是否可能完成所有课程？

样例
    例1:
    
    输入: n = 2, prerequisites = [[1,0]] 
    输出: true
    例2:
    
    输入: n = 2, prerequisites = [[1,0],[0,1]] 
    输出: false

一段没有想到给出的课程有10000多门而导致超时的代码

class Solution {
        
    public:
        /*
         * @param numCourses: a total of n courses
         * @param prerequisites: a list of prerequisite pairs
         * @return: true if can finish all courses or false
         */
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        
            // write your code here
            if(prerequisites.size()<=0) return true;
            vector<int>tmp(numCourses,0);
            queue<int> q;
            for (int i = 0; i < prerequisites.size(); i++) {
        
                tmp[prerequisites[i].first]++;
            }
            for (int i = 0; i < numCourses; i++) {
        
                if(tmp[i]==0) q.push(i);
            }
            while(!q.empty())
            {
        
                int num=q.front();
                q.pop();
                for (int i = 0; i < prerequisites.size(); i++) {
        
                    if(prerequisites[i].second==num)
                    {
        
                        tmp[prerequisites[i].first]--;
                        if(tmp[prerequisites[i].first]==0) q.push(prerequisites[i].first);
                    }
                }
            }
            for (int i = 0; i < numCourses; i++) {
        
                if(tmp[i]!=0) return false;
            }
            return true;
        }
    };

正确代码：如拓扑排序一样，先建立图的联系，然后bfs即可

class Solution {
        
    public:
        /*
         * @param numCourses: a total of n courses
         * @param prerequisites: a list of prerequisite pairs
         * @return: true if can finish all courses or false
         */
        struct node
        {
        
            int indegree;
            vector<int> neighbors;
            node(int x=0):indegree(x){
        }
        };
        
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        
            // write your code here
            vector<node> graph(numCourses);
            int cnt=0;
            for (auto i : prerequisites) {
        
                graph[i.first].indegree++;
                graph[i.second].neighbors.push_back(i.first);
            }
            queue<node> q;
            for (int i = 0; i < numCourses; i++) {
        
                /* code */
                if(graph[i].indegree==0)
                {
        
                    q.push(graph[i]);
                    cnt++;
                }
            }
            while(!q.empty())
            {
        
                node tmp=q.front();
                q.pop();
                for (int i = 0; i < tmp.neighbors.size(); i++) {
        
                    /* code */
                    int num=tmp.neighbors[i];
                    graph[num].indegree--;
                    if(graph[num].indegree==0) 
                    {
        
                        q.push(graph[num]);
                        cnt++;
                    }
                }
            }
            return cnt==numCourses;
        }
    };