AcWing 1977. 信息中继——并查集
原题链接
简单
作者:
Lg_970
,
2022-04-27 22:00:14
,
所有人可见
,
阅读 487
并查集
- 对每头牛 $i$ ,它和另一头牛 $a[i]$ ,参加的是同一个通信链,以此为依据建立并查集。
- 不会陷入循环的牛的特点:通信链到某头不通信的牛处结束。而不通信的牛一定是根牛。
- 找到所有通信链(集合)的根牛(并查集的根节点),如果根牛还存在联络对象(说明该通信链还没结束,这头牛还要联系一头牛,且这头牛也在这个集合内),则这是一个存在循环的通信链。
#include <bits/stdc++.h>
using namespace std;
int a[1010],p[1010],s[1010];
int find(int x){
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main(){
int n; 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)]=find(a[i]);
}
}
}
int res=0;
for(int i=1;i<=n;i++){
if(p[i]==i && a[i]==0)
res+=s[i];
}
cout << res;
return 0;
}
tql
tql
太厉害了