AtCoderBeginnerContest168復習＆まとめ（後半） - Qiita

AtCoder ABC168 2020-05-17(日)に行われたAtCoderBeginnerContest168の問題をA問題から順に考察も踏まえてまとめたものとなります． 後半ではDEFの問題を扱います．前半はこちら． 問題は引用して記載していますが，詳しくはコンテストページの方で確認してください． コンテストページはこちら 公式解説PDF D問題 .. (Double Dots) 問題文 あるところに、洞窟があります。 洞窟には$N$個の部屋と$M$本の通路があり、部屋には$1$から$N$の、通路には$1$から$M$の番号がついています。通路$i$は部屋$A_i$と部屋$B_i$を双方向につないでいます。どの$2$部屋間も、通路をいくつか通って行き来できます。部屋$1$は洞窟の入り口がある特別な部屋です。 洞窟の中は薄暗いので、部屋$1$以外の各部屋に$1$つずつ道しるべを設けるこ