103047: [Atcoder]ABC304 Ex - Constrained Topological Sort
Description
Score : $625$ points
Problem Statement
You are given a directed graph with $N$ vertices and $M$ edges. For $i = 1, 2, \ldots, M$, the $i$-th edge is directed from vertex $s_i$ to vertex $t_i$.
Determine whether there is a permutation $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$ that satisfies both of the following conditions, and if there is, provide an example.
- $P_{s_i} \lt P_{t_i}$ for all $i = 1, 2, \ldots, M$.
- $L_i \leq P_i \leq R_i$ for all $i = 1, 2, \ldots, N$.
Constraints
- $2 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq \min\lbrace 4 \times 10^5, N(N-1) \rbrace$
- $1 \leq s_i, t_i \leq N$
- $s_i \neq t_i$
- $i \neq j \implies (s_i, t_i) \neq (s_j, t_j)$
- $1 \leq L_i \leq R_i \leq N$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $s_1$ $t_1$ $s_2$ $t_2$ $\vdots$ $s_M$ $t_M$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$
Output
If there is no $P$ that satisfies the conditions, print No
. If there is a $P$ that satisfies the conditions, print Yes
in the first line, and the elements of $P$ separated by spaces in the second line, in the following format.
If multiple $P$'s satisfy the conditions, any of them will be accepted.
Yes $P_1$ $P_2$ $\ldots$ $P_N$
Sample Input 1
5 4 1 5 2 1 2 5 4 3 1 5 1 3 3 4 1 3 4 5
Sample Output 1
Yes 3 1 4 2 5
$P = (3, 1, 4, 2, 5)$ satisfies the conditions. In fact,
- for the first edge $(s_1, t_1) = (1, 5)$, we have $P_1 = 3 \lt 5 = P_5$;
- for the second edge $(s_2, t_2) = (2, 1)$, we have $P_2 = 1 \lt 3 = P_1$;
- for the third edge $(s_3, t_3) = (2, 5)$, we have $P_2 = 1 \lt 5 = P_5$;
- for the fourth edge $(s_4, t_4) = (4, 3)$, we have $P_4 = 2 \lt 4 = P_3$.
Also,
- $L_1 = 1 \leq P_1 = 3 \leq R_1 = 5$,
- $L_2 = 1 \leq P_2 = 1 \leq R_2 = 3$,
- $L_3 = 3 \leq P_3 = 4 \leq R_3 = 4$,
- $L_4 = 1 \leq P_4 = 2 \leq R_4 = 3$,
- $L_5 = 4 \leq P_5 = 5 \leq R_5 = 5$.
Sample Input 2
2 2 1 2 2 1 1 2 1 2
Sample Output 2
No
No $P$ satisfies the conditions, so print No
.
Input
题意翻译
给定一张 $n$ 个点 $m$ 条边的有向图,判断是否存在一个拓扑序 $P$ 满足 $P_i\in[L_i,R_i]$。 translated by cszyfOutput
问题描述
给你一个有向图,包含N个顶点和M条边。对于i = 1, 2, ..., M,第i条边是从顶点$s_i$指向顶点$t_i$的。
确定是否存在一个排列$P = (P_1, P_2, ..., P_N)$满足以下两个条件,如果存在,请给出一个例子。
- 对于所有i = 1, 2, ..., M,都有$P_{s_i} \lt P_{t_i}$。
- 对于所有i = 1, 2, ..., N,都有$L_i \leq P_i \leq R_i$。
约束条件
- $2 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq \min\lbrace 4 \times 10^5, N(N-1) \rbrace$
- $1 \leq s_i, t_i \leq N$
- $s_i \neq t_i$
- $i \neq j \implies (s_i, t_i) \neq (s_j, t_j)$
- $1 \leq L_i \leq R_i \leq N$
- 所有输入值都是整数。
输入
输入以标准输入的形式给出,格式如下:
$N$ $M$ $s_1$ $t_1$ $s_2$ $t_2$ $\vdots$ $s_M$ $t_M$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$
输出
如果不存在满足条件的$P$,输出No
。如果存在满足条件的$P$,在第一行输出Yes
,在第二行输出$P$中的元素,以空格分隔,格式如下。
如果存在多个满足条件的$P$,则任意一个都会被接受。
Yes $P_1$ $P_2$ $\ldots$ $P_N$
样例输入1
5 4 1 5 2 1 2 5 4 3 1 5 1 3 3 4 1 3 4 5
样例输出1
Yes 3 1 4 2 5
排列$P = (3, 1, 4, 2, 5)$满足条件。实际上,
- 对于第一条边$(s_1, t_1) = (1, 5)$,我们有$P_1 = 3 \lt 5 = P_5$;
- 对于第二条边$(s_2, t_2) = (2, 1)$,我们有$P_2 = 1 \lt 3 = P_1$;
- 对于第三条边$(s_3, t_3) = (2, 5)$,我们有$P_2 = 1 \lt 5 = P_5$;
- 对于第四条边$(s_4, t_4) = (4, 3)$,我们有$P_4 = 2 \lt 4 = P_3$。
同时,
- $L_1 = 1 \leq P_1 = 3 \leq R_1 = 5$,
- $L_2 = 1 \leq P_2 = 1 \leq R_2 = 3$,
- $L_3 = 3 \leq P_3 = 4 \leq R_3 = 4$,
- $L_4 = 1 \leq P_4 = 2 \leq R_4 = 3$,
- $L_5 = 4 \leq P_5 = 5 \leq R_5 = 5$。
样例输入2
2 2 1 2 2 1 1 2 1 2
样例输出2
No
不存在满足条件的$P$,因此输出No
。