Reverse and DAGAI (CI翻译)
Problem Statement
There is a simple directed graph $G$ with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the $i$-th edge goes from vertex $a_i$ to vertex $b_i$. It is guaranteed that $(a_i,b_i)\neq (b_j,a_j)$ for $i\neq j$. Also, an integer $K$ with $2 \leq K \leq N-2$ is given.
Determine whether it is possible to make $G$ a graph with no directed cycles (DAG) by performing the following operation zero or more times.
- Choose a size-
$K$subset$S$of$\lbrace 1,\ldots,N\rbrace$. For every directed edge whose both endpoints' numbers are in$S$, reverse its direction. - That is, if there is an edge from vertex
$u$to vertex$v\ (u,v\in S)$, delete that edge and add a directed edge from vertex$v$to vertex$u$. This operation is performed simultaneously for all applicable edges.
$T$ test cases are given; solve each of them.
Constraints
$1 \leq T \leq 50000$$4 \leq N \leq 2\times 10^5$$0 \leq M \leq \min({N(N-1), 2\times 10^5})$$2 \leq K \leq N-2$$1 \leq a_i, b_i \leq N$$a_i \neq b_i$$(a_i, b_i) \neq (a_j, b_j)$and$(a_i,b_i) \neq (b_j,a_j)$for$i\neq j$.- The sum of
$N$in each input is at most$2\times 10^5$. - The sum of
$M$in each input is at most$2\times 10^5$. - All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_TEach test case is given in the following format:
N M K
a_1 b_1
a_2 b_2
\vdots
a_M b_MOutput
Output the answers for $\mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T$ in this order in the following format.
Output Yes if it is possible to make $G$ a graph with no directed cycles (DAG) by performing the operation zero or more times, and No otherwise.
{"titleZh":"反转与 DAG","bodyZh":"## 题目描述\n\n给定一个具有 $N$ 个顶点和 $M$ 条边的简单有向图 $G$。顶点编号为 $1$ 至 $N$，第 $i$ 条边从顶点 $a_i$ 指向顶点 $b_i$。保证对于 $i\\neq j$，$(a_i,b_i)\\neq (b_j,a_j)$。此外，还给定一个满足 $2 \\leq K \\leq N-2$ 的整数 $K$。\n\n请判断是否可以通过执行以下操作零次或多次，将 $G$ 变为一个不含有向环的图（DAG）。\n\n- 选择一个大小为 $K$ 的子集 $S$，其中 $S$ 是 $\lbrace 1,\\ldots,N\\rbrace$ 的子集。对于两个端点的编号都在 $S$ 中的每条有向边，将其方向反转。\n- 也就是说，如果存在一条从顶点 $u$ 到顶点 $v\\ (u,v\\in S)$ 的边，则删除该边，并添加一条从顶点 $v$ 到顶点 $u$ 的有向边。对于所有符合条件的边，同时执行此操作。\n\n给定 $T$ 组测试用例，请解决每组测试用例。\n\n## 约束条件\n\n- $1 \\leq T \\leq 50000$\n- $4 \\leq N \\leq 2\\times 10^5$\n- $0 \\leq M \\leq \\min({N(N-1), 2\\times 10^5})$\n- $2 \\leq K \\leq N-2$\n- $1 \\leq a_i, b_i \\leq N$\n- $a_i \\neq b_i$\n- $(a_i, b_i) \\neq (a_j,b_j)$ 且 $(a_i,b_i) \\neq (b_j,a_j)$，其中 $i\\neq j$。\n- 所有测试用例中 $N$ 的总和不超过 $2\\times 10^5$。\n- 所有测试用例中 $M$ 的总和不超过 $2\\times 10^5$。\n- 所有输入值均为整数。\n\n## 输入格式\n\n输入从标准输入按以下格式给出：\n\n``\nT\n\\mathrm{case}_1\n\\mathrm{case}_2\n\\vdots\n\\mathrm{case}_T\n\n\n每组测试用例按以下格式给出：\n\n\nN M K\na_1 b_1\na_2 b_2\n\\vdots\na_M b_M\n\n\n## 输出格式\n\n按照以下格式，按顺序输出 \\mathrm{case}_1,\\mathrm{case}_2,\\ldots,\\mathrm{case}_T 的答案。\n\n如果可以通过执行该操作零次或多次将 $G$ 变为一个不含有向环的图（DAG），则输出 Yes；否则输出 No
样例
3
7 10 3
1 2
2 3
3 1
4 5
5 6
6 4
1 4
2 5
3 6
7 1
7 19 5
1 4
2 3
2 4
2 5
3 5
3 6
3 7
4 3
4 6
4 7
5 1
5 4
5 6
6 1
6 2
6 7
7 1
7 2
7 5
9 15 5
1 6
2 7
2 9
3 1
3 4
4 5
4 6
4 7
4 8
5 7
5 9
6 5
6 9
7 9
8 9
Yes
No
Yes
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。