返回

CodeForces 755C PolandBall and Forest

发布时间:2023-09-14 09:07:30 77

题目链接:​​http://codeforces.com/contest/755/problem/C​​​
题意:给你一个长度为n的序列,a[i]表示a[i]与i有条边相连,让你求这个序列构成的森林里有多少棵树
解析!:裸的并查集

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
int fa[maxn],a[maxn];
void init(int n)
{
for(int i=1;i<=n;i++)
fa[i] = i;
}
int getfa(int x)
{
if(fa[x]==x)
return fa[x];
return fa[x] = getfa(fa[x]);
}
void merge(int u,int v)
{
int t1 = getfa(u);
int t2 = getfa(v);
if(t1!=t2)
fa[t1] = t2;
}
int main(void)
{
int n,x;
scanf("%d",&n);
init(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
int t1 = getfa(x);
if(t1!=i)
merge(x,i);
}
int ans = 0;
for(int i=1;i<=n;i++)
{
if(fa[i]==i)
ans++;
}
printf("%d\n",ans);
return 0;
}

 

特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报
评论区(0)
按点赞数排序
用户头像
精选文章
thumb 中国研究员首次曝光美国国安局顶级后门—“方程式组织”
thumb 俄乌线上战争,网络攻击弥漫着数字硝烟
thumb 从网络安全角度了解俄罗斯入侵乌克兰的相关事件时间线
下一篇
CodeForces 792A New Bus Route 2023-09-14 06:16:53