建图然后深搜
我们假设有一个编号为0的牛,那么我们就可以把题意理解成每个牛发消息,最后编号为0的牛可以收到多少消息,那么我们可以把消息的发送和接收抽象成一个[接收者->发送者]的一条路,那么所有的这些路就可以构成一个图,那么从点0开始向外记忆化dfs就可以找到所有给0发消息的牛,然后计数就是我们最后想要的答案,由于每个节点最多访问到一次,那么最后的时间复杂度就是$O(n)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e3+10;
vector<int> road[N];
int tag[N],F[N],ans=0,book[N];
void dfs(int fa){
for(auto p:road[fa]){
if(book[p]) continue;
ans++;
book[p]=1;
dfs(p);
}
return;
}
int main(void){
int n;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>F[i];
road[F[i]].push_back(i);//编号为F[i]的牛会收到编号为i的牛的消息
}
dfs(0);
cout<<ans;
return 0;
}