问题描述
问题分析
明显的拓扑排序，但是这一题的条件有两个，除了给的限定条件外还应该优先按照从1~n输出。
所以考虑使用优先队列来取合适的点
考虑前面的应该尽量比后面的大，所以若用优先队列，则若正向建边，会导致队列中已有的上一层元素比后推入的元素大，从而使队列完全按照从大到小输出，产生错误结果。
所以考虑反向建边，则先取最一小级中最大的，并且每一次取当前队列中的最大的，则可以保证在按照1~n的顺序的情况下，按照特殊条件排序。
因为是反向建边，所以要把得到的结果倒序输出。
测试数据:
1
2
3
4
5
6
| 10
6 4
6 3
3 1
5 4
4 2
|
输出：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n;
int cnt[30200];
int topo[30200];
struct node {
int next;
int to;
} a[100200];
int head[30200];
void toposort() {
priority_queue<int>q;
for(int i=1; i<=n; i++)
if(!cnt[i]) {
q.push(i);
}
int t=0;
while(!q.empty()) {
int ttop=q.top();
q.pop();
topo[t++]=ttop;
for(int i=head[ttop]; i!=-1; i=a[i].next) {
cnt[a[i].to]--;
if(!cnt[a[i].to])
q.push(a[i].to);
}
}
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
int m;
scanf("%d %d",&n,&m);
memset(cnt,0,sizeof(cnt));
memset(head,-1,sizeof(head));
for(int i=0; i<m; i++) {
int u,v;
scanf("%d %d",&u,&v);
a[i].to=u;
a[i].next=head[v];
head[v]=i;
cnt[u]++;
}
toposort();
for(int i=n-1; i>=0; i--)
printf("%d%c",topo[i],i==0?'\n':' ');
}
return 0;
}
|