第一道拓扑排序题
每次删除入度为0的点，并输出
这题要求队名小的排前面，所以要用到重载的优先队列
1 #include<bits/stdc++.h> 2 using namespace std; 3 priority_queue<int,vector<int>,greater<int> > q;//优先队列默认是值越大，优先级越高，这里重载了，升序排列 4 int mapp[505][505],in[505]; 5 void topo(int n) 6 { 7 for(int i=1;i<=n;i++) 8 { 9 if(in[i]==0)q.push(i);//如果顶点的入度为0，入队 10 } 11 int c=1; 12 while(!q.empty()) 13 { 14 int v=q.top(); 15 q.pop(); 16 if(c<n) 17 { 18 printf("%d ",v); 19 c++; 20 }else 21 { 22 printf("%d ",v); 23 24 } 25 for(int i=1;i<=n;i++)//删除该顶点 26 { 27 if(!mapp[v][i]) 28 { 29 continue; 30 } 31 in[i]--;//目标顶点的入度减1 32 if(!in[i])q.push(i); //目标顶点入度==0，就入队 33 } 34 } 35 } 36 int main() 37 { 38 int n,m; 39 while(~scanf("%d %d",&n,&m)) 40 { 41 memset(mapp,0,sizeof(mapp)); 42 memset(in,0,sizeof(in)); 43 44 for(int i=0;i<m;i++) 45 { 46 int p1,p2; 47 scanf("%d %d",&p1,&p2); 48 if(mapp[p1][p2])continue; 49 else mapp[p1][p2]=1; 50 in[p2]++;//入度 51 } 52 topo(n); 53 } 54 55 return 0; 56 }