1.bfs

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=100010;
int n,m;
struct Node
{
    int id;
    Node* next;
    Node(int _id):id(_id),next(NULL){}
}*head[N];
int d[N],q[N];

void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}

bool topsort()
{
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
    {
        if(!d[i])
          q[++tt]=i;
    }
    while(hh<=tt)
    {
        int t=q[hh++];
        for(auto p=head[t];p;p=p->next)
        {
            if(--d[p->id]==0)
               q[++tt]=p->id;
        }
    }
    return tt==n-1;
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        d[b]++;
        add(a,b);
    }
    if(!topsort()) puts("-1");
    else
    {
        for(int i=0;i<n;i++)
          cout<<q[i]<<' ';
    }
    return 0;
}

2.dfs

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=100010;
int n,m;
struct Node
{
    int id;
    Node* next;
    Node(int _id):id(_id),next(NULL){}
}*head[N];
int st[N],q[N],top;

void add(int a,int b)
{
    auto p=new Node(b);
    p->next=head[a];
    head[a]=p;
}

bool dfs(int u)
{
    st[u]=1;

    for(auto p=head[u];p;p=p->next)
    {
        int j=p->id;
        if(!st[j])
        {
            if(!dfs(j)) return false;
        }
        else if(st[j]==1) return false;
    }

    q[top++]=u;
    st[u]=2;
    return true;
}

bool topsort()
{
    for(int i=1;i<=n;i++)
    {
        if(!st[i] && !dfs(i))
          return false;
    }
    return true;
}
int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    if(!topsort()) puts("-1");
    else
    {
        for(int i=n-1;i>=0;i--)
           cout<<q[i]<<' ';
    }
    return 0;
}

3.课程表
https://leetcode-cn.com/problems/course-schedule/

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& prerequisites) {
        vector<vector<int>> g(n);
        vector<int>d(n);
        for(auto&e :prerequisites)
        {
            int b=e[0],a=e[1];
            g[a].push_back(b);
            d[b]++;
        }

        queue<int>q;
        for(int i=0;i<n;i++)
        {
            if(d[i]==0)
              q.push(i);
        }

        int cnt=0;
        while(q.size())
        {
            auto t=q.front();
            q.pop();
            cnt++;
            for(auto i:g[t])
            {
                if(--d[i]==0)
                  q.push(i);
            }
        }

        return cnt==n;
    }
};

4.课程表ii

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
         vector<vector<int>> g(numCourses);
         vector<int>d(numCourses);

         for(auto&e : prerequisites)  //b-->a
         {
             int b=e[0],a=e[1];
             g[a].push_back(b);
             d[b]++;
         }
         queue<int>q;
         for(int i=0;i<numCourses;i++)
         {
             if(d[i]==0) q.push(i);
         }
         vector<int>res;
         while(q.size())
         {
             auto t=q.front();
             q.pop();
             res.push_back(t);
             for(auto i:g[t])
             {
                 if(--d[i]==0) q.push(i);
             }
         }

         if(res.size()<numCourses) return{};
         else return res;
    }
};