[Codeforces Round #445][Codeforces 886C]Petya and Catacombs

    题意：在一个完全图中（且每个点都有自环）从任意点出发，到达一个点时记录上一次到达这个点的时间，如果第一次到达这个点则记录下小于当前时间的随机数。给出记录下来的n个数，求图的最少点数。

    题解：设第i个数为\(x_i\)，从\(x_i\)到i连一条边。可以发现图中有n+1个点（包括0号点），n条边，正好构成了一棵树。容易发现在同一个点上走的方案对应树上的一条向根走的路径。题目即求最少的指向树根的链数使得这些链完全覆盖了n+1个点。

    显然答案即为叶子节点个数，因为一条这样的链最多只能覆盖到一个叶子节点，所以答案大于等于叶子节点数;而从每个叶子节点出发向根走直到不能继续走为止，刚好能覆盖所有点。

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;

int d[maxn];
int n;
int ans;

int main()
{
	scanf("%d",&n);
	for (int i=1,x;i<=n;i++) scanf("%d",&x),d[x]++;
	for (int i=1;i<=n;i++) if (d[i]==0) ans++;
	printf("%d\n",ans);
	return 0;
}