題上描述這種圖是很特殊的，每個頂點只有一條指出去的有向邊，而且一定存在一個環，哪怕是自環，從任意一個頂點出發，最終一定進入一個環。我們的任務的判斷這樣的兩個圖是否同構。

首先，這個圖不一定是弱連通的，可能會有多個連通分量，我們需要考慮每個連通分量。每個連通分量中一定存在一個環，去掉環上的邊以後，剩下 的是一個森林，每棵樹都是內向樹。實際上它是環狀內向樹森林。對於兩個內向樹，我們可以很容易地判斷它們是否同構，於是我們有了解決問題的方法。

首先是兩個內向樹，如果它們同構，它們的括號序列一定相同，反之也成立。判斷兩個環狀內向樹森林同構，首先應該滿足環的大小相同，如果兩 個環的頂點數都不一樣，那麼它們一定不會同構。如果環大小相同，則需要枚舉兩個環上的對應點，然後判斷以環上每個頂點爲根的內向樹是否都同構。用上述方法 可以判斷兩個連通分量是否同構，對於題中給的兩個圖，首先判斷連通分量的個數是否相同，然後用搜索的方法確定一個對應關係，以此判斷每個每對連通分量是否 同構。如果存在一種對應方案使得所有的連通分量通過，那麼這兩個圖同構。

上述方法中，生成所有內向樹括號序列需要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