TopCoder の解説は vexorian さんが書いてたときは分かりやすかった。
英語で読むのは面倒なので、かいつまんで日本語にする。

---
グラフで考える。
$\mathrm{f}(x) = y$ のとき、x → y と y → x の二種類の辺の張り方ができる。どちらでもいいが、
今回の問題では y → x という張り方だと、すべてのノードにおいて "ひとつ前のノード" というのは多くてひとつ（入次数が高々一個）になり、利便性が高いことに注目したい。
y → x というリンクがあるとき、
・集合から要素 y を取り除いたときは要素 x も取り除かなければならない
・集合に要素 x を含める場合は要素 y も含めなければならない
ということを意味する。

グラフには閉路が含まれる可能性があるが、強連結成分分解すれば DAG にできる。
この DAG においても入次数が高々一個、という特殊な状況は維持されており、この DAG は森になる。

森（複数の木）なので、再帰的に処理できる。
このとき、葉から根に向かって矢印を張るようにする（$\mathrm{parent\_of}$）。

#include <iostream>
#include <algorithm>
using namespace std;
using i64 = long long;

// 強連結成分 (Strongly Connected Components) 分解
// DFS 2回 O(V+E)
class SCC {
  int n;
  vector<vector<int>> fG, rG;
  vector<bool> used;
  vector<int> vertices; // 帰りがけ順の並び
  void dfs(int u);
  void rdfs(int v, int k);
public:
  SCC();
  SCC(int n); // 頂点数が n のグラフ
  void add_edge(int u, int v); // u から v に辺を張る
  void solve(); // 強連結成分分解する
  vector<vector<int>> restore_sccs(); // solve() の後に呼び出す。強連結成分をトポロジカル順序で返す
  int scc_count; // solve() の後に呼び出せる。強連結成分の個数
  vector<int> order; // solve() の後に呼び出せる。属する強連結成分のトポロジカル順序
};

// {{{ SCC実装
SCC::SCC() : n(0) {}

SCC::SCC(int n) : n(n) {
  fG.assign(n, vector<int>());
  rG.assign(n, vector<int>());
}

void SCC::add_edge(int u, int v) {
  fG[u].push_back(v);
  rG[v].push_back(u);
}

void SCC::dfs(int u) {
  used[u] = true;
  for(int v : fG[u]) {
    if(!used[v]) { dfs(v); }
  }
  vertices.push_back(u);
}

void SCC::rdfs(int v, int k) {
  used[v] = true;
  order[v] = k;
  for(int u : rG[v]) {
    if(!used[u]) { rdfs(u, k); }
  }
}

void SCC::solve() {
  used.assign(n, false);
  order.assign(n, 0);
  vertices.clear();
  for(int u=0; u<n; ++u) {
    if(!used[u]) { dfs(u); }
  }
  used.assign(n, false);
  scc_count = 0;
  for(int i=vertices.size()-1; i>=0; --i) {
    if(!used[vertices[i]]) { rdfs(vertices[i], scc_count++); }
  }
}

vector<vector<int>> SCC::restore_sccs() {
  vector<vector<int>> res(scc_count, vector<int>()); // res[scc_count][]
  for(int i=0; i<n; ++i) {
    res[order[i]].push_back(i);
  }
  return res;
} // }}}

class InvariantSets { public: i64 countSets(vector<int> f); };

SCC scc;
vector<int> parent_of;

// v番目の強連結成分のパターン数を求める
i64 solve(int v) {
  i64 res = 1;
  // vを含める: 全ての子の事象は互いに排反なので、それらのパターン数を掛ける
  for(int i=0; i<scc.scc_count; ++i) {
    if(parent_of[i] == v) { // リンクを逆に最終的に葉まで辿る。
      res *= solve(i);
    }
  }
  // vを含めない: 空集合の1個を足す
  return ++res;
}

i64 InvariantSets::
countSets(vector<int> f) {
  int n = f.size();
  ::scc = SCC(n);
  for(int i=0; i<n; ++i) {
    scc.add_edge(f[i], i);
  }
  scc.solve();
  vector<int> &order = scc.order; // 頂点iと頂点jが同じ強連結成分ならorder[i]==order[j]
  ::parent_of.assign(n, -1);
  for(int i=0; i<n; ++i) {
    if(order[i] != order[f[i]]) { // f[i] → i が異なる強連結成分への矢印なら
      parent_of[order[i]] = order[f[i]]; // 根に向かっていくような今までと逆のリンクを張る
    }
  }
  i64 res = 1LL;
  for(int i=0; i<scc.scc_count; ++i) {
    if(parent_of[i] == -1) { // リンクの終端（根）から
      res *= solve(i);  // 葉に向かう
    }
  }
  return res;
}
      

(ΦωΦ)＜あとがきへ