条件の意味について考えてみます．

\(1\) つ目の条件より，\(i \in T\) のとき \(i, f(i), f(f(i)), \cdots\) の全てが \(T\) に属します．\(S\) は有限なのである \(k > 0\) があって \(f^k(i)\) が \(f^l(i) (l < k)\) と等しくなります．そのような最小の \(k\) と，対応する \(l\) を取ると \(f^k(i)\) からは \(f^l(i), \cdots, f^{k-1}(i)\) の繰り返しになっています．(グラフ的に言うと，有向辺 \((i, f(i))\) を張ったグラフを考えると，各 (弱) 連結成分はサイクルに向かってパスが入っていく形をしています．) ここで \(l>0\) のとき，\(f^{l-1}(i) \neq f^{k-1}(i)\) ですが，\(f^l(i) = f^k(i)\) なので \(2\) つ目の条件に矛盾します．つまり\(i\) はサイクルに属し，また \(i \in T\) ならばサイクルの全ての頂点が \(T\) に属するということです．

明らかに条件はサイクルごとに独立なので，サイクルの個数が求まれば \(C\) として \(2^C-1\) が答えです．サイクルの個数は，グラフの形が特殊なので単純な連結成分の個数と一致します．計算量は \(\mathrm{O}(N)\) です．