POI2001 跳舞蝇的教练

题目:

  Byteland一直以奇妙的跳舞蝇而闻名于世。驯养的苍蝇能和着音乐的节奏精确地做每一次飞跃。通常,训练者会在桌上放一排硬币,这些硬币的排列并不按照特定的顺序。每枚硬币上都有一行题字:i→j,i是这枚硬币的编号,j是站在硬币i上的苍蝇下一步应该飞往的硬币编号。训练者在每个硬币上放一只苍蝇,然后开始放音乐。那些苍蝇就跟着音乐的节拍开始跳舞,在每一拍中苍蝇都会直接跳到编号为j的硬币上。在舞蹈中,可能会出现多只苍蝇在同一硬币上的情况。这样,跳舞蝇就会一起继续表演。假定有n只苍蝇,n枚硬币。则一旦确定了n枚硬币上的题字,那么这场表演也就确定了。然而,对硬币不同的设置也可能导致相同的表演,只要我们把硬币按适当的顺序排列。
  让我们先来看3枚硬币上的表演。
  如果表演是这样进行:
  从第一个硬币到第二个,第二个到第三个,第三个又回到第一个硬币(表示为1→2,2→3,3→1)。
  具体表演是3只苍蝇绕圈跳跃,从不相遇。那么表演1→2,2→3,3→3,则是与其不同的。
  因为该表演为:两拍后,所有的苍蝇在第3枚硬币上相遇,然后一直在原地跳跃。
  但是,设置1→2,2→3,3→2,4→4和1→1、2→3、3→2、4→3就是同样的类型。
  如果你把前者的硬币从左到右排列,而把后者从右到左排列,就会看到相同的表演。
  任务:
  如果跳舞蝇的两次表演是相同的,就会使观众不满,请编写一个程序:
  读入测试任务的个数;
  对每一个测试任务,从PCH.IN中读入两组硬币设置,验证是否能把硬币按一定顺序排列,使跳舞蝇给出相同的表演;

思路:

  讲道理题目十分难读,其实要求的就是判断两个基环内向树是否同构。
  先考虑把环拆开,那么就是判断每一棵有根树是否同构,可以考虑把树映射成括号序列。但是子树的顺序不影响树的同构关系,所以可以把子树的括号序列进行排序(也就说全部都求字典序最小的表示法)
  在环上也是一样,旋转这个置换找到最小的字典序。在不同的子图之间也是按照字典序排序。这样就能用 把图映射成一个序列。
  比如下图对应的序列就是(方括号用来分割每个子图):

  如果用哈希值来保存括号序列,用一种不容易冲突且满足交换律的运算符合并哈希值,就能做到 了。(可是我又懒得实现)

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 2005;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {mset(HEAD, 0); tot = 0;}
    void add(int x, T w) { NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w; }
    T& operator[] (int x) { return W[x]; }
};
Link<N, N, int> G;

bool mark[N], vis[N];
string dfs(int o) {
    mark[o] = true;
    vector<string> vec;
    erep(k, G, o) if(!mark[G[k]]) vec.push_back(dfs(G[k]));
    sort(ALL(vec));
    string ans = "(";
    for(string s : vec) ans = ans + s;
    return ans + ")";
}

string s[N];
int rt[N];
string getStr(int to[], int n) {
    mset(vis, 0); mset(mark, 0);
    G.clear(); rep(i, 1, n) G.add(to[i], i);
    vector<string> vec;
    rep(i, 1, n) {
        if(mark[i]) continue;
        int o = to[i], t, tot = 0;
        for(; !vis[o]; o = to[o]) vis[o] = true;
        t = o;
        do {
            rt[tot++] = t;
            mark[t] = true;
            t = to[t];
        } while(t != o);
        rep(i, 0, tot - 1) s[i] = dfs(rt[i]);
        int p = 0;
        rep(x, 1, tot - 1) 
            for(int _ = 1, i = p, j = x; _ <= tot; _++) {
                if(s[i] != s[j]) {
                    if(s[j] < s[i]) p = x;
                    break;
                }
                i = (i + 1) % tot; j = (j + 1) % tot;
            }
        string str = "[";
        rep(_, 1, tot) {
            str = str + s[p];
            p = (p + 1) % tot;
        }
        str = str + "]";
        vec.push_back(str);
    }
    sort(ALL(vec));
    string ans = "";
    for(string s : vec) ans = ans + s;
    return ans;
}

int a[N], b[N];
int main() {
    int cas, n;
    scanf("%d", &cas);
    while(cas--) {
        scanf("%d", &n);
        rep(i, 1, n) scanf("%d", a + i);
        rep(i, 1, n) scanf("%d", b + i);
        puts(getStr(a, n) == getStr(b, n) ? "T" : "N");
    }
    return 0;
}