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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
typedef pair<int,int> par;
int n, m, uu, vv, a[2005], b[2005], inn[2005], c[2005], hea[2005], cnt, k, e[2005];
par d[2005];
struct Edge{
int too, nxt;
}edge[10005];
bool cmp(par a, par b){
return a.second<b.second;
}
void add_edge(int fro, int too){
edge[++cnt].nxt = hea[fro];
edge[cnt].too = too;
hea[fro] = cnt;
}
int f(int o){
k = 0;
for(int i=1; i<=n; i++){
c[i] = inn[i];
if(!inn[i] && i!=o){
d[++k] = par(i, a[i]);
push_heap(d+1, d+1+k, cmp);
}
}
for(int i=n; i; i--){
if(!k) return i;
par x=d[1];
pop_heap(d+1, d+1+k, cmp);
k--;
if(x.second<i) return i;
for(int i=hea[x.first]; i; i=edge[i].nxt){
int t=edge[i].too;
c[t]--;
if(!c[t] && t!=o){
d[++k] = par(t, a[t]);
push_heap(d+1, d+1+k, cmp);
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
for(int i=1; i<=m; i++){
scanf("%d %d", &uu, &vv);
add_edge(vv, uu);
inn[uu]++;
}
for(int i=1; i<=n; i++){
c[i] = inn[i];
if(!inn[i]){
d[++k] = par(i, a[i]);
push_heap(d+1, d+1+k, cmp);
}
}
for(int i=n; i; i--){
par x=d[1];
pop_heap(d+1, d+1+k, cmp);
k--;
e[i] = x.first;
for(int i=hea[x.first]; i; i=edge[i].nxt){
int t=edge[i].too;
c[t]--;
if(!c[t]){
d[++k] = par(t, a[t]);
push_heap(d+1, d+1+k, cmp);
}
}
}
for(int i=1; i<=n; i++) printf("%d ", e[i]);
printf("\n");
for(int i=1; i<=n; i++) printf("%d ", f(i));
printf("\n");
return 0;
}
|