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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
#define LL long long
#define sk() (putchar(' '))
#define ek() (putchar('n'))
#define MAX 10005
using namespace std;
int (){
int x=0,flag=1;char ch=0;
while (ch<'0'||ch>'9'){
if (ch=='-') flag=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-48;
ch=getchar();
}
return x*flag;
}
void Write(int x){
if (x<0) x=-x,putchar('-');
if (x>9) Write(x/10);
putchar(x%10+48);
}
int n,m;
int edgenum,Edge[MAX<<1],head[MAX],nxt[MAX<<1];
void addedge(int x,int y){
Edge[++edgenum]=y;
nxt[edgenum]=head[x];
head[x]=edgenum;
}
int ddl[MAX];
int cdeg[MAX],deg[MAX];
int ans[MAX];
struct Node{
int x,ddl;
Node(int xx=0,int dd=0){
x=xx;ddl=dd;
}
friend bool operator < (Node x,Node y){
return x.ddl>y.ddl;
}
};
priority_queue<Node> q;
int ord[MAX];
void Sol(){
for (int i=1;i<=n;i++) deg[i]=cdeg[i];
while (!q.empty()) q.pop();
for (int i=1;i<=n;i++)
if (!deg[i]) q.push(Node(i,ddl[i]));
int t=0;
while (!q.empty()){
Node x=q.top();q.pop();
ord[++t]=x.x;
for (int i=head[x.x];i;i=nxt[i]){
int tmp=Edge[i];
if (!--deg[tmp]) q.push(Node(tmp,ddl[tmp]));
}
}
for (int i=n;i;i--)
Write(ord[i]),(i==1)? ek():sk();
}
void work(int s){
for (int i=1;i<=n;i++) deg[i]=cdeg[i];
while (!q.empty()) q.pop();
for (int i=1;i<=n;i++)
if (!deg[i]) q.push(Node(i,ddl[i]));
int t=0;
while (!q.empty()){
Node x=q.top();q.pop();
if (x.x==s) continue;
if (x.ddl>t+1){
ans[s]=n-t;
return;
}
t++;
for (int i=head[x.x];i;i=nxt[i]){
int tmp=Edge[i];
if (!--deg[tmp]) q.push(Node(tmp,ddl[tmp]));
}
}
ans[s]=n-t;
}
int main(){
n=Read(),m=Read();
for (int i=1;i<=n;i++) ddl[i]=n-Read()+1;
for (int i=1;i<=m;i++){
int x=Read(),y=Read();
addedge(y,x);cdeg[x]++;
}
Sol();
for (int i=1;i<=n;i++) work(i);
for (int i=1;i<=n;i++)
Write(ans[i]),(i==n)? ek():sk();
return 0;
}
|
近期评论