This post is written in Chinese. Please consider using Google Translate

题上描述这种图是很特殊的，每个顶点只有一条指出去的有向边，而且一定存在一个环，哪怕是自环，从任意一个顶点出发，最终一定进入一个环。我们的任务的判断这样的两个图是否同构。

首先，这个图不一定是弱连通的，可能会有多个连通分量，我们需要考虑每个连通分量。每个连通分量中一定存在一个环，去掉环上的边以后，剩下 的是一个森林，每棵树都是内向树。实际上它是环状内向树森林。对于两个内向树，我们可以很容易地判断它们是否同构，于是我们有了解决问题的方法。

首先是两个内向树，如果它们同构，它们的括号序列一定相同，反之也成立。判断两个环状内向树森林同构，首先应该满足环的大小相同，如果两 个环的顶点数都不一样，那么它们一定不会同构。如果环大小相同，则需要枚举两个环上的对应点，然后判断以环上每个顶点为根的内向树是否都同构。用上述方法 可以判断两个连通分量是否同构，对于题中给的两个图，首先判断连通分量的个数是否相同，然后用搜索的方法确定一个对应关系，以此判断每个每对连通分量是否 同构。如果存在一种对应方案使得所有的连通分量通过，那么这两个图同构。

上述方法中，生成所有内向树括号序列需要O(N^2logN)时间(需要排序)，枚举每个环的对应关系需要O(N)，判断两个内向树括号 序列相同需要O(N)，枚举连通分量间的对应关系由于是搜索，尽管实际搜索的很少，但是从时间复杂度上分析仍然是O(N!)。每个文件有D个测试数据，于 是总的时间复杂度是O((N^2logN+N^2N!)D)。但是实际上这个时间复杂度由于全部从最坏情况考虑(实际上所有最坏的情况不可能同时达 到)，所以是相当悲观的估计。实际编程对于N<=2000，已经可以完全应付了。

在编程实现的时候，许多地方要用到链表，否则空间是不够用的。细节不容忽视。

关于内向树以及生成括号序列，请参看有向树与树的括号序列表示法。

/* 
 * Problem: POI2001 pch
 * Author: Guo Jiabao
 * Time: 2009.2.5 14:05
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
using namespace std;
const int MAXN=4001,PERN=2000;
struct edge{int t;edge *next;};
struct sequence{int len;string s;};
struct subsq{int len;string *s;};
template <typename T> class linknode
{
    public:
        linknode *next;
        T s;
        linknode(T ts):next(0),s(ts){}
};
template <typename T> class linklist
{
    public:
        linknode<T> *f,*l;
        linklist():f(0),l(0){}
        void ins(T s)
        {
            if (l)l=l->next=new linknode<T>(s);
            else f=l=new linknode<T>(s);
        }
        void clear()
        {
            linknode<T> *a=f,*b;
            while (a){b=a;a=a->next;delete b;}
            f=l=0;
        }
};
int D,N,Ec,Bc,S1,S2;
int Bel[MAXN];//每个顶点所属连通分量
int TB[MAXN],TC; //暂存正向搜索的连通分量
linklist<int> Circle[MAXN]; //链表存储每个圈
bool inCircle[MAXN]; //记录每个节节点
bool used[MAXN]; //生成排列时DFS用到的记录数组
sequence seq[MAXN]; //每个子树的括号序列
int Cs[MAXN]; //每个圈的大小
edge E[MAXN*2];//边集的空间
edge *Ap[MAXN],*An[MAXN];//正图和逆图的邻接表
subsq S[MAXN];//暂存括号序列

void addedge(edge *&A,int t)
{
    if (A)
    {
        edge *t=A;
        A=&E[++Ec];
        A->next=t;
    }
    else
    {
        A=&E[++Ec];
        A->next=0;
    }
    E[Ec].t=t;
}

void init()
{
    int i,t;
    Ec=-1;Bc=0;
    memset(Ap,0,sizeof(Ap));
    memset(An,0,sizeof(An));
    scanf("%d",&N);
    for (i=1;i<=N;i++)
    {
        scanf("%d",&t);
        addedge(Ap[i],t);
        addedge(An[t],i);
        Bel[i]=0;
        seq[i].len=0;
        seq[i].s="";
        inCircle[i]=false;
    }
    for (i=PERN+1;i<=PERN+N;i++)
    {
        scanf("%d",&t);
        t+=PERN;
        addedge(Ap[i],t);
        addedge(An[t],i);
        Bel[i]=0;
        seq[i].len=0;
        seq[i].s="";
        inCircle[i]=false;
    }
}

void connect_dfs_n(int u) //逆向求连通分量
{
    Bel[u]=Bc;
    for (edge *k=An[u];k;k=k->next)
    {
        int v=k->t;
        if (!Bel[v])
            connect_dfs_n(v);
    }
}

int connect_dfs_p(int u) //正向求连通分量，并查找圈
{
    Bel[u]=Bc;
    TB[++TC]=u;
    int v=Ap[u]->t;
    if (!Bel[v])
    {
        int r=connect_dfs_p(v);
        if (r)
        {
            ++Cs[Bc];
            Circle[Bc].ins(u);
            inCircle[u]=true;
            if (r==u)
                return 0;
            else
                return r;
        }
        else
            return 0;
    }
    else
    {
        ++Cs[Bc];
        Circle[Bc].ins(u);
        inCircle[u]=true;
        if (u==v) v=0;
        return v;
    }
}

void connect(int A,int B)
{
    for (int i=A;i<=B;i++)
    {
        if (!Bel[i])
        {
            Bc++;
            Cs[Bc]=0;
            TC=0;
            connect_dfs_p(i);
            for (int j=1;j<=TC;j++)
                connect_dfs_n(TB[j]);
        }
    }
}

inline int cmp(const void *a,const void *b)
{
    return  ((subsq *)a)->s->compare(*(((subsq *)b)->s)) ;
}

void TreeSeq(int u)//求内向树序列
{
    linklist<subsq> LL;
    subsq T;
    int L=0;
    ++seq[u].len;
    seq[u].s+='(';
    for (edge *k=An[u];k;k=k->next)
    {
        int v=k->t;
        if (inCircle[v]) continue;
        TreeSeq(v);
        T.s=&seq[v].s;
        T.len=seq[v].len;
        LL.ins(T);
    }
    for (linknode<subsq> *p=LL.f;p;p=p->next)
        S[++L]=p->s;
    qsort(S+1,L,sizeof(S[0]),cmp);
    for (int i=1;i<=L;i++)
    {
        seq[u].s+=*(S[i].s);
        seq[u].len+=S[i].len;
    }
    ++seq[u].len;
    seq[u].s+=')';
    LL.clear();
}

bool compare(int a,int b)
{
    if (Cs[a]!=Cs[b]) return false; //圈大小不相等
    linknode<int> *k,*l,*pl;
    for (pl=Circle[b].f;pl;pl=pl->next) //枚举偏移量
    {
        l=pl;
        for (k=Circle[a].f;k;k=k->next)
        {
            int x=k->s,y=l->s;
            if (!(l=l->next)) l=Circle[b].f;
            if (seq[x].len!=seq[y].len || seq[x].s!=seq[y].s) //内向树序列不相同
                break;
        }
        if (!k)
            return true;
    }
    return false;
}

bool arrange_dfs(int k) //生成两图连通分量对应关系的排列
{
    if (k>S1)
        return true;
    for (int i=S1+1;i<=S2;i++)
        if (!used[i] && compare(k,i))
        {
            used[i]=true;
            bool b=arrange_dfs(k+1);
            used[i]=false;
            if (b) return true;
        }
    return false;
}

bool solve()
{
    int i,j;
    init();
    connect(1,N);S1=Bc;
    connect(1+PERN,N+PERN);S2=Bc;
    if (S1!=S2-S1) //1..S1为图1的连通分量 S1+1..S2为图2的连通分量
        return false; //两图连通分量个数不相等
    for (i=1;i<=S2;i++)
        for (linknode<int> *k=Circle[i].f;k;k=k->next)
            TreeSeq(k->s); //计算以每个圈上顶点为根的内向树括号序列
    return arrange_dfs(1);
}

void clear()
{
    for (int i=1;i<=S2;i++)
        Circle[i].clear();
}

int main()
{
    int i;
    freopen("pch.in","r",stdin);
    freopen("pch.out","w",stdout);
    scanf("%d",&D);
    for (i=1;i<=D;i++)
    {
        if (solve())
            printf("Tn");
        else
            printf("Nn");
        clear(); //清理 释放内存
    }
    return 0;
}

<h2><span class="mw-headline">跳舞蝇的教练 </span></h2>

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中读入两组硬币设置，验证是否能把硬币按一定顺序排列，使跳舞蝇给出相同的表演；

• 把结果写入文件。

  输入：

  文件的第一行是测试任务的个数d(1≤d≤100)，以下3*d行，每三行描述一个任务。三行中的第一行是一个整数 n(1≤n≤2000)，表示硬币的个数。后两行每行均为一套硬币的描述。格式为n个用空格分开的1…n范围内的整数，第i个整数表示硬币i上的苍蝇应该 飞向的硬币的编号。

  输出：

  对每个任务，均要在文件中输出一行，仅包含一个字母。如果可以按一定顺序排硬币使表演相同则输出“T”，否则输出“N”。

  输入样例：

  2
    3
    2 3 1
    2 3 3
    4
    2 3 2 4
    1 3 2 3

  输出样例：

  N
    T