lc课程表 拓扑排序第二天背诵

//用queue做
 const int N = 100010;
class Solution {
public:
int h[N], e[N], ne[N], idx;
int d[N];
int n;
    void add(int a, int b)
    {
    e[idx]=b, ne[idx]=h[a], h[a]=idx++;
    }

    bool canFinish(int num, vector<vector<int>>& p) {
    memset(h,-1,sizeof h);
    int o=0;
    queue<int> q;
    for(auto x:p){
        add(x[1],x[0]);
        d[x[0]]++;
    }
    for(int i = 0;i < num;i ++)
        if(!d[i]){
            q.push(i);
            o ++;
            }
        while(!q.empty())
        {
            int t = q.front(); q.pop();
            for(int j = h[t]; ~j ;j = ne[j])
            {
                if(-- d[e[j]] == 0)
                {
                    o ++;
                    q.push(e[j]);
                }
            }
        }
    if(o==num)return true;
    return false;
    }
};
----------
//数组模拟队列
const int N = 100010;
class Solution {
public:
int h[N], e[N], ne[N], idx;
int d[N],q[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
bool topsort(int n)
{
int hh = 0, tt = -1;//模拟队列
for (int i = 0; i < n; i ++ )
    if (!d[i])
        q[ ++ tt] = i;
while (hh <= tt)
{
    int t = q[hh ++ ];
    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (-- d[j] == 0)
            q[ ++ tt] = j;
    }
}
return tt == n - 1;//有向无环图全部入队，tt == n - 1
}
bool canFinish(int num, vector<vector<int>>& p) 
{
    memset(h, -1, sizeof h);
    for(int i = 0;i < p.size();i++)
    {
    add(p[i][1],p[i][0]);
    d[p[i][0]]++;
    }
    if(topsort(num)) return true;
    return false;
}
};