MovingTokens_AC.cpp

#include <bits/stdc++.h>
using namespace std;

struct edge{int pu, pv, move;};

struct MovingTokens {
    int move(int n, int m, vector<int> moves) {
        vector<edge> rev_edges[50][50];
        for(int j=0;j<m;j++){
            for(int pu=0;pu<n;pu++){
                for(int pv=0;pv<n;pv++){
                    int u = moves[j*n + pu], v = moves[j*n + pv];
                    rev_edges[u][v].push_back((edge){pu, pv, j});
                }
            }
        }

        bool equiv[50][50];
        int next[50][50];
        memset(equiv, 0, sizeof(equiv));

        queue<pair<int, int>> que;
        for(int i=0;i<n;i++){
            equiv[i][i] = true;
            que.emplace(i, i);
        }

        while(que.size()){
            auto p = que.front(); que.pop();
            int u = p.first, v = p.second;
            for(edge e: rev_edges[u][v]){
                int pu = e.pu, pv = e.pv;
                if(!equiv[pu][pv]){
                    equiv[pu][pv] = true;
                    next[pu][pv] = e.move;
                    que.emplace(pu, pv);
                }
            }
        }

        vector<bool> boxes(n, true);
        while(true){
            bool change = false;
            for(int i=0;i<n;i++){
                if(!boxes[i]) continue;
                for(int j=i+1;j<n;j++){
                    if(!boxes[j] || i == j || !equiv[i][j]) continue;
                    change = true;
                    int u = i, v = j;
                    while(u != v){
                        int move = next[u][v];
                        vector<bool> next_boxes(n, false);
                        for(int k=0;k<n;k++){
                            if(boxes[k]) next_boxes[moves[move*n + k]] = true;
                        }
                        boxes = next_boxes;
                        u = moves[move*n + u];
                        v = moves[move*n + v];
                    }
                }
            }
            if(!change) break;
        }

        int ans = 0;
        for(int i=0;i<n;i++){
            if(boxes[i]) ans++;
        }
        return ans;
    }
};