AcWing 1977. 信息中继
原题链接
简单
作者:
Ysfsblj
,
2022-04-28 11:05:34
,
所有人可见
,
阅读 157
$O(n)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int p[N], s[N], a[N], n;
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
//本题不是标准的循环问题,只要到0就算不循坏
//所以找到所有多次转移后会到0的点的合集就是答案
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) p[i] = i, s[i] = 1;
for(int i = 1; i <= n; i++){
cin >> a[i];
if(a[i]){
if(find(i) != find(a[i])){
s[find(a[i])] += s[find(i)];
p[find(i)] = p[find(a[i])];
}
}
}
int res = 0;
for(int i = 1; i <= n; i++){
if(a[i] == 0) res += s[i];
}
cout << res << "\n";
return 0;
}