No.100 直列あみだくじ

1,...,n の順列(置換)のなかから該当のものを抜き出すという問題。
愚直にやると n! だが置換が巡回置換の積であるということを用いれば、各巡回置換(下のコードでは group)を独立して確定してやればよいので O(N^3)
group 構築時に自己ループ判定が抜けてバグった。
dfs で書くと、無駄に save_xx 変数を用意しないで済むみたいだし、 used フラグは N <= 60 なんで int64 にもたせると bit 演算でフラグ管理ができるっぽい。(参考 yukicoder : No.100 直列あみだくじ - kmjp's blog)

class SeriesAmidakuji {
public:
    bool make_group(vector<int> &s, int start, vector<bool> &used, const vector<int> &A) {
            vector<int>  save_s = s;    // 上書きされるので
            vector<bool> save_u = used; // 上書きされるので
            int cur = start;

            do {
                if (s[cur] == A[cur]) // 自己ループはダメ
                    return false;
                s[s[cur]] = A[cur]; // group を埋める
                cur = s[cur];
            } while (cur != start);

            // ループがずれていることもあるので再度チェック
            cur = start;
            do {
                used[cur] = true; // 使用数字を更新
                if (s[s[cur]] != A[cur]) // ダメだった
                {   // もどす
                    s    = save_s;
                    used = save_u;
                    return false;
                }
                cur = s[cur];
            } while (cur != start);
            return true;
    }
    void solve(void) {
            int N;
            cin>>N;
            vector<int> A(N);
            REP(i,N)
            {
                cin>>A[i];
                --A[i];
            }

            // 1,...,N の置換 s のうち
            // s^2 = A なるものを見つける
            //
            // 置換は巡回置換の積として表現できる。
            // s = s1*s2*...*sr
            //
            // 巡回置換の個数は最大 N なので全探索でできる。
            //
            vector<int> s(N,-1);
            vector<bool> used(N,false);
            REP(i,N)
            {   // 自己ループは先に埋める
                if (i == A[i])
                {
                    s[i] = i;
                    used[i] = true;
                }
            }

            // 巡回置換ごとに独立なので各 group をうめる
            // 厳密には A = s^2 = (s1^2)*...*(sr^2) が巡回置換の積になっていて、
            // (s1^2) 内部での数字の遷移はその外の数字の遷移には影響を与えないため独立して決定できる。
            //
            // O(N^3)
            REP(i,N) // i -> ... からはじまる group
            {
                if (s[i] >= 0)  // すでに確定済み
                    continue;
                REP(j,N)
                {
                    if (i==j) // 自己ループになりうるものはすでに処理済みなので飛ばす
                        continue;
                    if (used[j])
                        continue;
                    // i->j から始まるとして group を作ってみる
                    s[i] = j;
                    if (make_group(s,i,used,A))
                        break; // 巡回置換毎に独立なので i から始まるグループは確定
                    s[i] = -1;
                }
                if (s[i] < 0) // i から始まるグループで条件を満たすものはなかった
                {
                    cout<<"No"<<endl;
                    return;
                }
            }
            cout<<"Yes"<<endl;

    }
};