前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 207. Course Schedule(拓扑排序)

LeetCode 207. Course Schedule(拓扑排序)

作者头像
ShenduCC
发布2020-02-20 13:20:51
3410
发布2020-02-20 13:20:51
举报
文章被收录于专栏:算法修养算法修养

题意:有n门课程,就是n个顶点,有m个对应关系:x,y,表示只有先上了y,才能上x。也就是x到y有一条有向边。问你求是否存在环。

题解:对于有向图求是否存在环,可以用拓扑排序,拓扑排序就是寻找入度为0的顶点,然后删去,并减少相邻点的入度,再寻找入度为0的点,直到所有顶点都删去,如果存在换,那么一定会有一些点是无法删除的。

代码语言:javascript
复制
class Solution {
public:
    
    vector<int> edge[10005];
    int a[10005];
    int b[10005];
    int vis[10005];
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        if(numCourses==0||numCourses==1)
            return true;
        
        if(prerequisites.size()==0)
            return true;
        
        for(int i=0;i<prerequisites.size();i++)
        {
            edge[prerequisites[i][1]].push_back(prerequisites[i][0]);
            a[prerequisites[i][0]]++;
            b[prerequisites[i][1]]++;
        }
        
        int num=0;
        while(1)
        {
            int tag=0;
            for(int i=0;i<numCourses;i++)
            {
                if(vis[i]==1)
                    continue;
                if(a[i]!=0)
                    continue;
                
                for(int j=0;j<edge[i].size();j++)
                {
                    a[edge[i][j]]--;
                }
                
                num++;
                tag=1;
                    
                vis[i]=1;
            }
            if(tag==0)
                break;
        }
        
        if(num != numCourses)
            return false;
        return true;
        
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-02-14 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档