問題一覧 > 通常問題

No.1023 Cyclic Tour

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 : chocoruskchocorusk / テスター : tarattata1tarattata1
14 ProblemId : 4008 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-04-08 14:23:48

問題文

yuki国には $1, 2, \ldots , N$ の番号がついた $N$ 個の街と、$1, 2, \ldots , M$ の番号がついた $M$ 本の道があります。道 $i$ ($1\leq i\leq M$) は街 $a_i$ と街 $b_i$ を結んでいます。$c_i=1$ のとき道 $i$ は双方向に通行可能で、$c_i=2$ のとき道 $i$ は街 $a_i$ から街 $b_i$ の方向にしか通行できません。

ラスク君は、適当な街からスタートして、道を通っていくつかの街を訪れてから元の街に帰ってくるという観光計画を立てようとしています。ここで、始点以外の街を $1$ つ以上訪れなければならず、終点以外で同じ街を二度訪れたり、同じ道を二度通ることがないようにしたいです。これが可能かどうか判定してください。

入力

$N\ M$
$a_1\ b_1\ c_1$
$a_2\ b_2\ c_2$
$:$
$a_M\ b_M\ c_M$

  • $2\leq N\leq 10^5$
  • $1\leq M\leq 2\times 10^5$
  • $1\leq a_i, b_i\leq N$
  • $1\leq c_i\leq 2$
  • $a_i\neq b_i$
  • $c_i=1$ のとき $a_i < b_i$
  • $i\neq j$ のとき $(a_i, b_i, c_i)\neq (a_j, b_j, c_j)$
  • 入力はすべて整数である。

出力

ある街からスタートして、同じ街、同じ道を二度通ることなく元の街に帰ってくることが可能ならば Yes と、不可能ならば No と出力せよ。

サンプル

サンプル1
入力
4 4
1 3 1
2 4 2
2 3 1
4 3 2
出力
Yes

街 $2$ からスタートして、道 $2$, $4$, $3$ を通って街 $2\to 4\to 3\to 2$ と移動すればよいです。

サンプル2
入力
4 5
1 2 1
3 1 2
3 2 2
3 4 1
4 2 2
出力
No

サンプル3
入力
2 3
1 2 1
1 2 2
2 1 2
出力
Yes

サンプル4
入力
4 2
1 2 1
3 4 2
出力
No

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。