题目详情题解（0）讨论（0）提交记录（0）

AT_agc077_c.[AGC077C] Reverse and DAG

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

$ N $ 頂点 $ M $ 辺の単純有向グラフ $ G $ があります．頂点には $ 1 $ から $ N $ の番号が付いており， $ i $ 番目の辺は頂点 $ a_i $ から頂点 $ b_i $ へ張られています． $ i\neq j $ のとき $ (a_i,b_i)\neq (b_j,a_j) $ であることが保証されます．また $ 2 $ 以上 $ N-2 $ 以下の整数 $ K $ が与えられます．

以下の操作を $ 0 $ 回以上好きな回数行うことで， $ G $ を有向閉路を含まないグラフ（DAG）にできるか否かを判定してください．

  • $ \lbrace 1,\ldots,N\rbrace $ のサイズ $ K $ の部分集合 $ S $ を選ぶ．始点と終点の番号がともに $ S $ に含まれるような有向辺すべてについて，その向きを反転させる．
    • すなわち，頂点 $ u $ から頂点 $ v\ (u,v\in S) $ に辺が張られているとき，その辺を削除し，頂点 $ v $ から頂点 $ u $ への有向辺を追加する．この操作はすべての対象の辺に対して同時に行われる．

$ T $ 個のテストケースが与えられるので，それぞれについて答えを求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

$ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $

各テストケースは以下の形式で与えられる．

$ N $ $ M $ $ K $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_M $ $ b_M $

输出格式

$ \mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T $ に対する答えを順に以下の形式で出力せよ．

操作を $ 0 $ 回以上好きな回数行うことで $ G $ を有向閉路を含まないグラフ（DAG）にできるならば Yes ，できないならば No と出力せよ．

输入输出样例

  • 输入#1

    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

    输出#1

    Yes
No
Yes

说明/提示

Sample Explanation 1

$ 1 $ 番目のテストケースでは，以下のように $ 2 $ 回の操作を行うことで $ G $ を有向閉路を含まないグラフにできます．

  • $ 1 $ 回目の操作では $ S = \lbrace 1, 2,7 \rbrace $ として操作を行う． 始点と終点の番号がともに $ S $ に含まれるような有向辺は頂点 $ 1 $ から頂点 $ 2 $ へ張られた辺と，頂点 $ 7 $ から頂点 $ 1 $ へ張られた辺である．これらの辺の向きが反転する．
  • $ 2 $ 回目の操作では $ S = \lbrace 4, 5,7 \rbrace $ として操作を行う． 始点と終点の番号がともに $ S $ に含まれるような有向辺は頂点 $ 4 $ から頂点 $ 5 $ へ張られた辺である．この辺の向きが反転し， $ G $ は有向閉路を含まないグラフになる．

$ 2 $ 番目のテストケースでは，どのように操作を行っても $ G $ を有向閉路を含まないグラフにできません．

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 $
  • $ i\neq j $ ならば $ (a_i, b_i) \neq (a_j, b_j) $ かつ $ (a_i,b_i) \neq (b_j,a_j) $
  • 一つの入力に含まれる $ N $ の総和は $ 2\times 10^5 $ 以下
  • 一つの入力に含まれる $ M $ の総和は $ 2\times 10^5 $ 以下
  • 入力される数値は全て整数

输入解题思路，AI测评打分。不知道怎么写?

首页