perogram

No.416 旅行会社

Quiz

https://yukicoder.me/problems/no/416

Submit

https://yukicoder.me/submissions/339563

解法

  • 破壊される辺以外を張っておく
  • 破壊クエリを逆から読みながらその辺を復活させていく
  • 木がつながったかはUnion Findで管理する
  • 辺を繋げる前に、今回の接続で初めて「点1とつながっている木」「点1とつながっていない木」が接続されるなら、それは破壊で通れなくなった日である
  • 「点1とつながっていない木」が隔離される日がわかったので、「点1とつながっていない木」のノード全てをdfsで走査して、日にちを書き込む

参考にしたもの

  • 公式解法
  • はむこさん

サンプル1

f:id:peroon:20190418115508j:plain