题目大意
有$n$头奶牛,编号$1$到$n$,第$i$头奶牛可以将信息传给编号为$F_i$奶牛,若$F_i$为$0$说明这头奶牛不能传信息给别的牛。问哪些奶牛的信息不会陷入死循环。
解题思路
$dfs$做法
$dfs$判断当前这头牛能不能传到一头不传消息的牛那里去,如果能则$res++$。$dfs$第二个参数是这个消息被传了几次,$times$大于$n$说明肯定是死循环了,那么就$return false$
并查集做法
可以发现,信息中断一定发生在不传消息的牛。每次合并集合让$f[i]$这头牛作为父亲,$i$这头牛作为儿子。最后若有连通块的根节点是一头不传消息的牛(这表示这个连通块内的牛在传消息时最后都会传到这个根牛,在根牛这里停下传递信息),那么答案加上这块连通块内点的数量。
具体代码
$dfs$做法
#include<iostream>
using namespace std;
const int N=1010;
int f[N];
int n;
bool dfs(int x,int times)
{
if(x==0) return true;
if(times>n) return false;
return dfs(f[x],times+1);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>f[i];
int res=0;
for(int i=1;i<=n;i++)
{
if(dfs(f[i],1)) res++;
}
cout<<res<<endl;
return 0;
}
并查集做法
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int p[N],f[N],s[N],n;
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>f[i];
s[i]=1;
p[i]=i;
}
for(int i=1;i<=n;i++)
{
if(f[i])
{
if(find(i)!=find(f[i]))
{
s[find(f[i])]+=s[find(i)];
p[find(i)]=find(f[i]);
}
}
}
int res=0;
for(int i=1;i<=n;i++)
if(p[i]==i&&f[i]==0)
res+=s[i];
cout<<res<<'\n';
return 0;
}