• 欢迎光临~

CF755C

开发技术 开发技术 2022-08-06 次浏览

题目简化和分析:

这题不用说怎么分析了吧,这一看就是个并查集求连通分量个数的经典模板。

我们需要将 (i)(p_i) 进行合并。

遍历每个 (i)(i+1) 是否属于同一个集合。

  • 属于不管。
  • 不属于贡献增加,并合并。

注意范围!

Solution:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int long long
const int N=1e4+50;
const int mod=1e9+7;
int t,n;
int p[N],a[N];
int find(int x){
	if(x!=p[x]) return p[x]=find(p[x]);
	return p[x]; 
}
signed main()
{
		scanf("%lld",&n);
		for(int i=1;i<=n;++i) p[i]=i;		
		for(int i=1;i<=n;++i){
			scanf("%lld",&a[i]);
			int fx=find(i),fy=find(a[i]);
			if(fx!=fy){
				p[fx]=fy;
			}
		}
		int ans=1;
		for(int i=1;i<n;++i){
			int fx=find(i),fy=find(i+1);
			if(fx!=fy){
				ans++;
				p[fx]=fy;
			}
		}
		printf("%lldn",ans);
}
程序员灯塔
转载请注明原文链接:CF755C
喜欢 (0)