小明要去一个国家旅游。这个国家有 N 个城市,编号为 1 至 N,并且有 MM 条道路连接着,小明准备从其中一个城市出发,并只往东走到城市 i 停止。
所以他就需要选择最先到达的城市,并制定一条路线以城市 i 为终点,使得线路上除了第一个城市,每个城市都在路线前一个城市东面,并且满足这个前提下还希望游览的城市尽量多。
现在,你只知道每一条道路所连接的两个城市的相对位置关系,但并不知道所有城市具体的位置。现在对于所有的 i,都需要你为小明制定一条路线,并求出以城市 i 为终点最多能够游览多少个城市。
第 1 行为两个正整数 N,M。
接下来 M 行,每行两个正整数 x,y,表示了有一条连接城市 x 与城市 y 的道路,保证了城市 x 在城市 y 西面。
N 行,第 i 行包含一个正整数,表示以第 i 个城市为终点最多能游览多少个城市。
5 6
1 2
1 3
2 3
2 4
3 4
2 5
xxxxxxxxxx
1
2
3
4
3
时间限制:1 s
内存限制:256 M
100% 的数据保证 1≤n≤100000,1≤m≤200000
x
int head[M], to[M], nt[M], cnt_edge;
int rudu[N];
inline void add_edge(int a, int b) {
to[++cnt_edge] = b;
++rudu[b];
nt[cnt_edge] = head[a];
head[a] = cnt_edge;
return ;
}
int n, m;
int cnt[N];
int q[M], l, r;
inline void Topological_sorting() {
while (l < r) {
int tp = q[l++];
for (int i = head[tp]; i; i = nt[i]) {
//if (rudu[to[i]] == 0) continue; //有向图,入度为0的点不会重新走,故这句代码可以省略
//cnt[to[i]] = max(cnt[to[i]], cnt[tp] + 1); //队列,后来的比前面的大,直接更新,可以忽略这代码
cnt[to[i]] = cnt[tp] + 1;
if (--rudu[to[i]] == 0) {
q[r++] = to[i];
}
}
}
return ;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d %d", &a, &b);
add_edge(a, b);
}
for (int i = 1; i <= n; i++) {
if (rudu[i] == 0) {
cnt[i] = 1;
q[r++] = i;
}
}
Topological_sorting();
for (int i = 1; i <= n; i++) printf("%d\n", cnt[i]);
return 0;
}