本文共 2671 字，大约阅读时间需要 8 分钟。

Description

给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。

Input

输入包含多组，每组格式如下。

第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10)

后面m行每行两个整数a b，表示从a到b有一条有向边。

Output

Sample

Input

1 02 21 22 1

Output

YESNO

答案：

#include 
   
    #include
    
     #define ll long longconst int N = 5e4 + 10;using namespace std;int mp[25][25];  //图的建立int in[25];  //记录入度int q[111];  //队列int main(){       int n,m;    while(cin>>n>>m)    {           memset(mp,0,sizeof(mp));  //数组清零        memset(in,0,sizeof(in));   //入度清零        int head=0,tail=0;  //清空队列        while(m--)   //图的建立        {               int a,b;            cin>>a>>b;            mp[a][b]=1;  //a->b 单向联通            mp[a][b]=mp[b][a]=1;  //a<->b双向联通            in[b]++;  //b对应入度+1        }        int i;        for(i=1; i<=n; i++) //找到入度为零的点        {               if(!in[i])            {                   q[tail++]=i;  //入度为零的点入队            }        }        int cnt=0; //计数        while(head
    
   

vector实现：

#include 
   
    #include
    
     #define ll long long#define inf 0x3f3f3f3fconst int N = 11;using namespace std;vector
     
      mp[N];int in[N];void Toposort(int n){       vector
      
        zero;  //入度为0的点    vector
       
         ans;  //排序结果    int i;    for(i=1;i<=n;i++)  //找到入度为零的点    {           if(!in[i])  //入度为零的点入队            zero.push_back(i);    }    while(!zero.empty())  //队列不为空    {           int pos=zero.back();        zero.pop_back();        ans.push_back(pos);        int len=mp[pos].size();        for(i=0;i
        
         >n>>m) { memset(mp,0,sizeof(mp)); memset(in,0,sizeof(in)); while(m--) { int a,b; cin>>a>>b; mp[a].push_back(b); in[b]++; } Toposort(n); } return 0;}
        
       
      
     
    
   

stl队列

#include 
   
    #include
    
     #define ll long long#define inf 0x3f3f3f3fconst int N = 11;using namespace std;int mp[N][N];int in[N];void Toposort(int n){       queue
     
      q;    int i;    for(i=1; i<=n; i++)    {           if(!in[i])            q.push(i);    }    int cnt=0;    while(!q.empty())    {           int top=q.front();        q.pop();        cnt++;        in[top]--;        for(i=1; i<=n; i++)        {               if(mp[top][i])            {                   in[i]--;                if(!in[i])                {                       q.push(i);                }            }        }    }    if(cnt==n)        cout<<"YES"<
      
       >n>>m)    {           memset(mp,0,sizeof(mp));        memset(in,0,sizeof(in));        while(m--)        {               int a,b;            cin>>a>>b;            mp[a][b]=1;            in[b]++;        }        Toposort(n);    }    return 0;}
      
     
    
   

拓扑排序讲解：[传送门](https://docs.qq.com/doc/DTmRnbHFYR3RGVkRx)