题目描述: 给你几组关系,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;
}
} 
京公网安备 11010502036488号