ARC114 B - Special Subsets (400)
点$ aから点$ f(a)に辺を延ばすと条件を満たす部分は閉路になっている
それぞれの閉路を含む、含まないが独立に選べるので答えは$ 2^{閉路の数} - 1
全てを使わないのは選べないので引く
コンテスト中はDFSで閉路を探していたが、この問題では連結成分の数と同じなのでUnion-Findとかでも良い
全ての要素を高々2回見るので$ O(N)
問題: https://atcoder.jp/contests/arc114/tasks/arc114_b
提出: https://atcoder.jp/contests/arc114/submissions/20936264
#ARC114 #400pt #B #ARC #AtCoder
#O(N)