デンソークリエイトプログラミングコンテスト2022 Winter (AtCoder Beginner Contest 280) F - Pay or Receive (500)
連結成分を求めて連結成分毎に以下を行う
DFSをしてループがあるかを検出する
いずれかのループで開始時と一周してきたときのポイントが異なるものがあればそれを使うか逆方向に回ることで無限ループ可能
そうで無い場合適当な辺を使って木を作る
ここに無い辺を使うとポイントが変わるなら無限ループが作れる
始点と終点の適当な共通祖先へ行ったときのポイントの和が答え
頂点に固定するのが簡単
問題: https://atcoder.jp/contests/abc280/tasks/abc280_f
提出: https://atcoder.jp/contests/abc280/submissions/36991826
#デンソークリエイトプログラミングコンテスト2022Winter #デンソークリエイトプログラミングコンテスト #ABC280 #500pt #F #ABC #AtCoder
#閉路検出