图论找环
时间复杂度 $O(n)$
B[]数组中某个位置的奶牛相当于占据了A[]数组中原来在这个位置上的奶牛的位置,可以建立一条有向边(即B[]->A[])
那么可以发现每一头奶牛都会抢占一个新的位置(也可能位置不变,也就是自环)
不是自环的话就一定是若干头(≥2头)奶牛之间形成一个环
而我们只需要找到所有环的个数(除开自环)即为循环移位组数,所有环中(除开自环)长度最大的就是最长的一组循环移位的长度
Java 代码
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static final int N = 110;
static int [] a = new int[N], b = new int[N]; //记录位置信息
static int [] ne = new int[N]; //记录某个节点的下一个节点是谁,也就是某头奶牛要到的新位置现在是哪头奶牛
static boolean [] mark = new boolean[N]; //记录某头奶牛的访问情况(是否已经遍历过)
static int n;
public static void main(String [] args) throws IOException {
n = Integer.parseInt(in.readLine());
for(int i = 1; i <= n; ++i) a[i] = Integer.parseInt(in.readLine());
for(int i = 1; i <= n; ++i) {
b[i] = Integer.parseInt(in.readLine());
ne[b[i]] = a[i]; //b[i] --> a[i] (b[i]奶牛来到了a[i]奶牛原本在的地方)
}
int times = 0, len = -1; //times: 循环移位组数 len: 最长的一组循环移位的长度
for(int i = 1; i <= n; ++i) {
if(mark[i] || i == ne[i]) continue; //已经遍历过的和自环的跳过
int res = 0; //存当前环的长度
for(int j = i; !mark[j]; j = ne[j], ++res) //只要还未遍历过就可以继续走
mark[j] = true; //遍历过的打上标记
len = Math.max(len, res); //取较大的值更新len
++times; //循环移位组数加一
}
out.write(times + " " + len + "\n");
in.close();
out.close();
}
}
讲的很清楚 , 恍然大悟
(^o^)/~