狙击手

N个狙击手，每个狙击手瞄准一个人（这个人有可能是他自己！）。所有狙击手不会同时***。你可以随意安排所有狙击手***的次序，直到无法再***为止，问：经过一番厮杀之后，最多幸存几个狙击手、最少幸存几个狙击手？

这个问题是两问：一问是狙击手最多活几个，一问是狙击手最少活几个。
一眼看上去，狙击手之间构成的结构是图。而实际上，这个图非常特殊：每个狙击手只能瞄准一个人，所以每个结点的出度必然是1，而入度可以很多。

首先考虑最多幸存几个狙击手。很显然，那些未被瞄准的人必然会幸存下来。但是这些人是一定要***的。这些“必然不死者”乱枪过后，会拯救一批新的“必然不死者”，“必然不死者”***之后又会拯救不死者，这样一直到全部“不死者”都无法***为止。所以这个问题可以用优先队列来解决：优先让必然不死者***（他们是一定要***的）。

接下来考虑最少幸存几个狙击手。这就需要深刻理解这个问题的特殊之处：每个结点出度为1。需要看清楚“单出度图”的一个特点：如果含有环，只能是形如“0”和形如“6”这样的环，不可能出现形如“8”的环。而每个形如6的环最少幸存一个人。于是，问题转化为：整个图中有多少个“6”。

import java.util.*; public class Main { class Node { int id, cnt;
    Node(int id, int cnt) { this.id = id; this.cnt = cnt;
    }
} int nonzero(boolean died[]) { int s = 0; for (int i = 1; i < died.length; i++) { if (!died[i]) s++;
    } return s;
}
Main() {
    Scanner cin = new Scanner(System.in); int N = cin.nextInt(); int a[] = new int[N + 1]; int b[] = new int[N + 1];//bi表示想杀i的人的个数 for (int i = 1; i <= N; i++) {
        a[i] = cin.nextInt();
    } for (int i = 1; i <= N; i++) b[a[i]]++;
    PriorityQueue<Node> q = new PriorityQueue<>(Comparator.comparing(x -> x.cnt)); for (int i = 1; i <= N; i++) {
        q.add(new Node(i, b[i]));
    } boolean died[] = new boolean[N + 1]; for (int i = 1; i <= N; i++) if (a[i] == i) died[i] = true; while (!q.isEmpty()) { int now = q.poll().id; if (died[now]) continue; if (!died[a[now]]) {
            died[a[now]] = true; int next = a[a[now]];//我的下下家得到解放 b[next]--;
            q.add(new Node(next, b[next]));
        }
    } int maxLive = nonzero(died);
    Arrays.fill(died, false); for (int i = 1; i <= N; i++) if (a[i] == i) died[i] = true; int ring[] = new int[N + 1];//ring i是否在环上 for (int i = 1; i <= N; i++) ring[i] = i; for (int i = 1; i <= N; i++) { if (died[i]) continue; int now = i; while (!died[a[now]] && a[now] != i) {
            died[a[now]] = true;
            now = a[now];
        } if (a[now] == i) {//如果成环了，要让环的祖先承担后续损失 int j = i; while (true) {
                ring[j] = i;
                j = a[j]; if (j == i) break;
            }
        } if (ring[a[now]] != a[now]) {
            died[ring[a[now]]] = true;
        }
    } int minLive = nonzero(died);
    System.out.println(minLive);
    System.out.println(maxLive);
} public static void main(String[] args) { new Main();
}
}