AcWing 1921. 重新排列奶牛（环图）

【题目描述】
农夫约翰的$N$头奶牛排成一排，编号$1\sim N$。
它们的排序可以由一个数组$A$来描述，其中$A(i)$是位于位置$i$的奶牛的编号。
约翰希望将它们重新排列为一个不同的顺序。
新顺序用数组$B$来描述，其中$B(i)$是位于位置$i$的奶牛的编号。
假设奶牛开始时的顺序为：

A = 5 1 4 2 3

并假设约翰希望它们重新排列为：

B = 2 5 3 1 4

为了从$A$顺序重新排列为$B$顺序，奶牛们进行了许多“循环”移位。
所谓循环移位，是指挑选排列中的若干头奶牛分在一组，组中奶牛进行循环移动位置，即第一头奶牛移动至第二头奶牛的位置，第二头奶牛移动至第三头奶牛的位置，以此类推，最后一头奶牛移动至第一头奶牛的位置。
如上例中，将$5,1,2$号奶牛分在一组进行循环移位，移动过后，$5$号奶牛移动至位置$2$，$1$号奶牛移动至位置$4$，$2$号奶牛移动至位置$1$；将$4,3$号奶牛分在另一组进行循环移位，移动过后，$4$号奶牛位于位置$5$，$3$号奶牛位于位置$3$；最终完成重新排列。
每头奶牛都恰好参与一组循环移位，除非其在$A,B$中的位置没有变化。
请计算奶牛们完成重新排列，共需多少组循环移位，最长的一组循环移位的长度是多少。

【输入格式】
第一行包含整数$N$。
接下来$N$行包含$A(i)$。
再接下来$N$行包含$B(i)$。

【输出格式】
输出循环移位的组数，以及最长的一组循环移位的长度。
如果不存在循环移位，则第二个数输出$-1$。

【数据范围】
$1\le N\le 100$
$1\le A(i),B(i)\le N$

【输入样例】

5
5
1
4
2
3
2
5
3
1
4

【输出样例】

2 3

【分析】

---

我们先将$A$中的每个元素所在的位置向其在新序列$B$中所在的位置连一条有向边，例如对于样例，我们连接这几条边：$1\to 2,2\to 4,4\to 1,3\to 5,5\to 3$。那么就形成了两个环分别为$1,2,4$和$3,5$。这两个环也就是我们要找的两组循环移位的数所在的位置，即共有两组数需要循环移位，最长的一组循环移位的长度为$3$。

---

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110;
int a[N], idx[N], st[N];//a表示原顺序，idx[i]表示奶牛i在新顺序中所在的位置
int n, cnt, res;//cnt表示环的数量，res表示最长环的长度(均不考虑自环)

int main()
{
    
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++)
    {
    
        int x;
        cin >> x;
        idx[x] = i;
    }
    for (int i = 0; i < n; i++)
    {
    
        int len = 0;
        for (int j = i; !st[j]; j = idx[a[j]])
            st[j] = true, len++;
        if (len > 1) cnt++, res = max(res, len);
    }
    if (!cnt) cout << 0 << ' ' << -1 << endl;
    else cout << cnt << ' ' << res << endl;
    return 0;
}