ARC114 B Special Subsets
問題を
$ N
頂点の, 頂点
$ i
から
$ f_i
に辺を張った
$ N
辺のグラフとしてとらえる. するとある連結成分内の頂点はその連結成分を選ぶならすべて選ばなければ条件を満たさないことから, 連結成分を選ぶかどうかを決めればよいことになる. 以上より, 答えは空集合は条件を満たさないことに注意すると連結成分の個数を
$ s
として
$ 2^s - 1
となる. 連結成分の個数はUnion-Findなどを用いて高速に求められる.
実装例:
https://atcoder.jp/contests/arc114/submissions/20932616