leetcode 210. 课程表 II 拓扑排序

题目描述

leetcode 210. 课程表 II

---

思路

不是所有图都可以进行拓扑排序
只有有向无环图才可以进行拓扑排序
有向无环图也称为拓扑图
一个有向无环图，一定至少存在一个入度为0的点。
拓扑排序不是唯一的。

拓扑排序思路：

1. 记录一下所有点的入度
2. 遍历入度表，把入度为0的点加入队列
3. 不断从队列头部拿出已经入队的入度为0的点，将与它关联的边另一头的点的入度删掉
4. 在这个过程中，如果有新的点的入度为0了，则入队
5. 直到所有点都被遍历完
6. 在这个过程中，用st数组，防止访问过的点被重复访问

---

代码

class Solution {
private:
    int r[2010];//入度表
    bool st[2010]; //判重数组
    int h[2010],e[4010],ne[4010],idx=0;  //数组模拟邻接表
    //这里h的大小和图中的点数是一个规模的，而e和ne的大小和图中的边数是一个规模的，所以不能太小
public:
    void add(int a,int b)  //在邻接表上加一条边
    {
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        memset(r,0,sizeof(r));
        memset(st,0,sizeof(st));
        memset(h,-1,sizeof(h));  //初始化为全-1

        for(int i=0;i<prerequisites.size();i++)
        {  //遍历一遍关系，建立邻接表和入读表
            add(prerequisites[i][1],prerequisites[i][0]);
            r[prerequisites[i][0]]++;
        }

        vector<int> k;
        int q[2010],tt=-1,hh=0;  //数组模拟队列
        //先遍历一遍入度表，把所有入度为0的点都入队，他们之间的先后顺序无所谓
        for(int i=0;i<numCourses;i++)
            if(r[i]==0)
            {
                q[++tt]=i;
                st[i]=true;
                k.push_back(i);
            }
        
        while(hh<=tt)
        {
            int t=q[hh];
            hh++;
            for(int i=h[t];i!=-1;i=ne[i])
            {
                int j=e[i];
                if(!st[j])  //没被访问过
                {
                    r[j]--;  //把当前点删去，相应的入度减一
                    if(r[j]==0)  //如果产生了新的入度为0的点，入队
                    {
                        q[++tt]=j;
                        st[j]=true;
                        k.push_back(j);
                    }
                }
            }
        }
        if(tt==(numCourses-1)) 因为数组模拟队列，队尾tt的位置可以反映从头到尾一共有多少元素进过队
            return k;
        else
        {
            k.clear();
            return k;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

---