AcWing 1977. 信息中继-基环树
原题链接
简单
作者:
CCoisini
,
2022-05-10 00:27:04
,
所有人可见
,
阅读 164
枚举法
枚举每个点检查是否包含在环内或者基环树上
# include <iostream>
# include <algorithm>
using namespace std;
const int N = 1010;
int cnt[N];
int ne[N];
int res;
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>ne[i];
for(int i=1;i<=n;i++)
{
int cnt =0;
int j=i;
while(ne[j]!=0&&cnt<=n) j=ne[j],cnt++;
if(ne[j]==0||cnt<=n) res++;
}
cout<<res;
}
并差集
检查每个点所在树的根结点是否还有后继,若有说明该点在基环树上,没有后继则这棵树上的点都不会陷入循环
# include <iostream>
# include <algorithm>
using namespace std;
const int N = 1010;
int p[N],ne[N];
int res;
int n;
int find(int a)
{
if(p[a]!=a) p[a] = find(p[a]);
return p[a];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) p[i] = i;
for(int i=1;i<=n;i++)
{
cin>>ne[i];
int j = ne[i];
p[find(i)] = find(j);
}
for(int i=1;i<=n;i++)
{
int k = find(i);
if(!ne[k]) res++;
}
cout<<res<<endl;
}