AcWing 1977. 信息中继
原题链接
简单
作者:
曦薇
,
2022-04-28 09:56:27
,
所有人可见
,
阅读 151
思路
- 可以用并查集来做,如果要合并的两个节点在一个集合里面,那么会成环,而且该集合中的所有节点消息都会进入循环,所以把根节点进行标记,然后在所有合并操作后遍历一下有多少点的根节点未被标记,就代表没有进入循环。
- 时间复杂度大致为 $O(n)$ ,空间复杂度为 $O(n)$ 。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int fa[N];
bool st[N];
int find(int x){
if(fa[x]!=x){
fa[x]=find(fa[x]);
}
return fa[x];
}
int main(void){
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++){
fa[i]=i;
}
int t;
for(i=1;i<=n;i++){
scanf("%d",&t);
if(t==0){
continue;
}
if(find(i)==find(t)){
st[find(i)]=true;
}else{
fa[find(i)]=find(t);
}
}
int ans=0;
for(i=1;i<=n;i++){
if(!st[find(i)]){
//cout<<i<<endl;
ans++;
}
}
printf("%d\n",ans);
return 0;
}