No.2674 k-Walk on Bipartite
タグ : / 解いたユーザー数 78
作問者 : nu50218 / テスター : Xelmeph null ngtkana NokonoKotlin 👑 eoeo
問題文
グラフの頂点 $s, t$ に対して、「 $s$ から隣接頂点への移動を $k$ 回繰り返して $t$ へ移動する経路」のことを $s$ から $t$ への長さ $k$ の歩道と呼びます。
まず始めに、eoeo はこのような問題を考えました。
頂点集合 $V$ と辺集合 $E$ からなる単純無向二部グラフ $G$ 、その頂点 $s, t$、正整数 $k$ が与えられます。 グラフ $G$ に $s$ から $t$ への長さ $k$ の歩道が存在するか判定してください。
しかしこのままではシンプルすぎます。 nu50218 は上の問題に一捻り加えて、辺集合 $E$ の代わりに $E$ から $0$ 本以上の辺を削除した $F$ を入力として与えることにしました。 改変された以下の問題を解いてください。
単純無向二部グラフ $G$ の頂点数 $N$ 、辺集合の部分集合 $F \subseteq E$、頂点 $s, t$、正整数 $k$ が与えられます。
与えられた情報のみから、グラフ $G$ に $s$ から $t$ への長さ $k$ の歩道が
- 存在すると確定するとき
Yes
、 - 存在しないと確定するとき
No
、 - 上記のいずれでもないとき
Unknown
を出力してください。
形式的な問題文
より厳密には、グラフ $(V, F)$ を部分グラフとして含む任意の $N$ 頂点からなる単純無向二部グラフ $H$ について
- 必ずグラフ $H$ に $s$ から $t$ への長さ $k$ の歩道が存在するとき
Yes
を、 - 必ずグラフ $H$ に $s$ から $t$ への長さ $k$ の歩道が存在しないとき
No
を
出力し、上記のいずれでもないとき Unknown
を出力してください。
入力
入力は以下の形式で標準入力から与えられます。
グラフの $N$ 個の頂点はそれぞれ $1, 2, \dots, N$ と番号付けられています。
$M = |F|$ であり、 $A_i, B_i$ は $F$ の $i$ 本目の辺の端点です。
$N$ $M$ $s$ $t$ $k$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$
出力
標準出力へ一行で出力し、最後に改行してください。
制約
入力は以下の制約を満たします。
- 入力はすべて整数
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq M \leq 2 \times 10^5$
- $1 \leq s, t \leq N$
- $1 \leq k \leq 10^9$
- $1 \leq A_i < B_i \leq N$
- $i \neq j$ ならば $(A_i, B_i) \neq (A_j, B_j)$
- グラフ $(V, F)$ は二部グラフである
サンプル
サンプル1
入力
4 3 1 4 5 1 2 2 3 3 4
出力
Yes
辺集合 $E$ は、 $F$ または $F$ に 辺 $\{1, 4\}$ を加えたものです。 後者の場合、たとえば頂点 $1$ から頂点 $4$ への長さ $5$ の歩道として $1 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 4$ が存在します。
サンプル2
入力
4 3 1 3 3 1 2 2 3 3 4
出力
No
辺集合 $E$ は、 $F$ または $F$ に 辺 $\{1, 4\}$ を加えたものです。 いずれの場合も、頂点 $1$ から頂点 $3$ への長さ $3$ の歩道は存在しないことが示せます。
サンプル3
入力
4 3 1 4 1 1 2 2 3 3 4
出力
Unknown
辺集合 $E$ は、 $F$ または $F$ に 辺 $\{1, 4\}$ を加えたものです。 後者の場合、たとえば頂点 $1$ から頂点 $4$ への長さ $1$ の歩道として $1 \rightarrow 4$ が存在します。 一方で、前者の場合には存在しないことが示せます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。