F2. Checker for Array Shuffling（图论/判DAG）

题目 题意：定义从数组 b b b到 a a a的伤心值为从 b b b转化到 a a a的最小交换次数，其中 b b b是 a a a的一个排列。给定数组 a a a，数组 b b b，问 b b b到 a a a的伤心值，是否为所有 a a a的排列中，最大的。

参考

同F1，我们给出结论。

证明：数组 b b b到 a a a的伤心值的最大值，为 n − c n t n-cnt n−cnt，其中 c n t cnt cnt为数组 a a a的出现次数最多的元素。 我们将从 b b b到 a a a的转化过程整合为交换位置的集合 { ( l 1 , r 1 ) , ( l 2 , r 2 ) , . . . ( l m , r m ) } \{(l_1,r_1),(l_2,r_2),...(l_m,r_m)\} {(l1​,r1​),(l2​,r2​),...(lm​,rm​)}，这里 r i r_i ri​有唯一性。因为如果 s w a p ( p o s j , p o s i ) , s w a p ( p o s k , p o s i ) swap(pos_j,pos_i),swap(pos_k,pos_i) swap(posj​,posi​),swap(posk​,posi​)，我们可以将其转化为 s w a p ( p o s j , p o s k ) , s w a p ( p o s j , p o s i ) swap(pos_j,pos_k),swap(pos_j,pos_i) swap(posj​,posk​),swap(posj​,posi​)。 我们将每次交换当成一条有向边，那么从 b b b到 a a a的转化过程等价为若干个有向树(DAG)的集合，其中每个DAG的点没有重复的，且每个DAG的边数等于其点数-1（树的定义）。 由于出现次数最多的元素次数为 c n t cnt cnt，因此我们最少需要构成 c n t cnt cnt个DAG。 因此最多的交换次数=所有DAG的边数= n − c n t n-cnt n−cnt

要判定 b b b到 a a a的转化是不是最大的伤心值，我们只需看 b b b到 a a a的转化中得到的有向图，是否由 c n t cnt cnt个DAG组成。我们标记图中出现次数最大的元素，然后看剩下的图中，是否为DAG即可。

#include 
using namespace std;
const int maxn = 200010;

int n;
int a[maxn], b[maxn];
vector ve[maxn];
bool vis[maxn], onstack[maxn], cyc;
void dfs(int u) {
	if (cyc) {
		return;
	}
	vis[u] = onstack[u] = 1;
	for (auto v: ve[u]) {
		if (onstack[v]) {
			cyc = true;
			return;
		}
		if (!vis[v])
			dfs(v);
	}
	onstack[u] = 0;
}
void solve() {
	scanf("%d", &n);
	for (int i = 0; i