题意:给出一个n个点有向图,问是否存在三个点,这三个点构成一个回路。n<=5000
模拟即可。
注意是必须三个点 多了居然不行。
import java.util.*;
public class Main { public static final int maxn = 5000;
public static int [] v = new int [maxn+10];
public static int [] f = new int [maxn+10]; public static int DFS(int x, int t) {
if (v[x]>0) return t - v[x];
v[x] = t;
int k = DFS(f[x], t+1);
v[x] = 0;
return k;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); for (int i = 1; i<=n; i++) f[i] = input.nextInt();
boolean flag = true;
for (int i = 1; i<=n; i++) {
if (3 == DFS(i, 1)) {
System.out.println("YES");
flag = false;
break;
}
}
if(flag) System.out.println("NO");
input.close();
} }