题目描述: 给你几组关系,q,p表示q 大于p现在让你从大到小输出这些数据
分析:拓扑模板 用bfs跑 (题目要求输出小的在前所以用优先队列),每次选入度为0的节点入队 注意的一点就是会有重复的数据(太坑了)
#include<bits/stdc++.h> #define pb(x) push_back(x) #define FOR(i,j,n) for(int i=j;i<n;i++) #define WE(t) while(t--) #define mp(x,y) make_pair(x,y) #define ms(a,x) memset(a,x,sizeof(a)) using namespace std; int main(){ int m,n; while(scanf("%d %d",&n,&m)!=EOF){ int degree[505]; int mapp[505][505]; ms(mapp,0); ms(degree,0); WE(m){ int x,y; cin>>x>>y; if(mapp[x][y]==0){ mapp[x][y]=1; degree[y]++; } } priority_queue<int,vector<int>,greater<int> >que; FOR(i,1,n+1){ if(degree[i]==0) que.push(i); } int flag=true; while(!que.empty()){ int now=que.top();que.pop(); if(flag) {cout<<now;flag=0;} else cout<<' '<<now; FOR(i,1,n+1){ if(mapp[now][i]){ degree[i]--; if(degree[i]==0) que.push(i); } } } cout<<endl; } }