/jd/jd
刚 VP AHOI2022 时 T1 又摸出来了一次这个东西，记一下比较好。
知识
往往的，都是形如 \(i\to p_i\)，这样的连边，保证了，每个点的出度为 \(1\)，每个点的入度为 \(1\)。
考虑每个点的出度为 \(1\)，则一定是一个由若干基环内向树组成的森林（一棵基环内向树，非根点唯一出边连其父亲，根连到其子树的某个儿子上，若根不是这样，则两棵树显然可以合并）。
考虑每个点的入度为 \(0\)，则一定是一棵基环外向树森林。
反正你摸来摸去得到的结论是，其图一定是由若干个简单环组成的。
那么对于一个环内，每跳环长步，回到原点，则若想所有的环都回到原点，显然最小步数是他们环长的 lcm。
考虑若原先有 \(p_i,p_j\)，我们交换 \(p_i,p_j\) 会咋样。
若原先不在一个环。
交换后变成这样！
那么，是不是两个环合并了！
若原先在一个环。
交换！
你会发现分裂出两个环了！
简单例题
发现是 \(i\to p_i\) 连边，随便做即可。
标签：连边,基环,AHOI2022,置换,入度,jd,出度 From： https://www.cnblogs.com/xugangfan/p/17245488.html