模板-判断某有向图是否存在拓扑序列

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int MAXV=1001;
int N,M;
int in[MAXV],init[MAXV];
vector<int> Adj[MAXV];

//Topo()用于判断某有向图是否存在拓扑序列
bool Topo()
{
    int num=0;
    queue<int> q;
    for(int i=0; i<N; i++)
    {
        if(in[i]==0)
            q.push(i);
    }
    while(!q.empty())
    {
        int u=q.front();
        //printf("%d",u);//输出拓扑序列顶点(由头至尾),注意该函数在返回true情形下也只能产生唯一一个拓扑序列
        q.pop();
        for(int i=0; i<Adj[u].size(); i++)
        {
            int v=Adj[u][i];
            in[v]--;
            if(in[v]==0)
                q.push(v);
        }
        num++;
    }
    if(num==N)
        return true;
    return false;
}
int main()
{

    cin>>N>>M;
    int u,v;
    for(int i=0; i<M; i++)
    {
        cin>>u>>v;
        Adj[u-1].push_back(v-1);//储存出度顶点
        in[v-1]++;//统计入度数
    }
    if(Topo())
        cout<<"该图存在拓扑序列"<<endl;
    else
        cout<<"该图不存在拓扑序列"<<endl;
    return 0;
}
/*
输入:
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
输出:
该图存在拓扑序列


输入:
3 2
2 1
2 3
输出:
该图存在拓扑序列
*/