第一道拓扑排序题
每次删除入度为0的点，并输出
这题要求队名小的排前面，所以要用到重载的优先队列
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;//优先队列默认是值越大，优先级越高，这里重载了，升序排列
int mapp[][],in[];
void topo(int n)
{
for(int i=;i<=n;i++)
{
if(in[i]==)q.push(i);//如果顶点的入度为0，入队
}
int c=;
while(!q.empty())
{
int v=q.top();
q.pop();
if(c<n)
{
printf("%d ",v);
c++;
}else
{
printf("%d\n",v); }
for(int i=;i<=n;i++)//删除该顶点
{
if(!mapp[v][i])
{
continue;
}
in[i]--;//目标顶点的入度减1
if(!in[i])q.push(i); //目标顶点入度==0，就入队
}
}
}
int main()
{
int n,m;
while(~scanf("%d %d",&n,&m))
{
memset(mapp,,sizeof(mapp));
memset(in,,sizeof(in)); for(int i=;i<m;i++)
{
int p1,p2;
scanf("%d %d",&p1,&p2);
if(mapp[p1][p2])continue;
else mapp[p1][p2]=;
in[p2]++;//入度
}
topo(n);
} return ;
}