就离谱,这个时间怎么回事(玄一关)
  • 板块灌水区
  • 楼主__Rickysun__
  • 当前回复13
  • 已保存回复13
  • 发布时间2024/10/5 16:14
  • 上次更新2024/10/5 17:32:02
查看原帖
就离谱,这个时间怎么回事(玄一关)
824205
__Rickysun__楼主2024/10/5 16:14

首先这个是题目,本蒟蒻为了复习CSP,重刷了一遍这道题,然后发生了一件令本蒟蒻百思不得其解的事情:

这是我以前的AC代码:

#include<bits/stdc++.h>
using namespace std;
int f[100010], ch[100010], n, k;
int find(int x) {
	if (f[x] == x) return x;
	else return f[x] = find(f[x]);
}
void merge(int x, int y) {
	int fx = find(x), fy = find(y);
	if (fx != fy) {
		f[fx] = fy;
		ch[fy] += ch[fx];
	}
}
int main() {
	int x, y;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		f[i] = i;
		ch[i] = 1;
	}
	for (int i = 1; i <= k; i++) {
		cin >> x >> y;
		merge(x, y);
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (f[i] == i) cnt++;
	}
	cout << cnt;
	return 0;
}

然后现在我重新写了一遍:(码风前后相差较大,不喜勿喷)

#include<bits/stdc++.h>
using namespace std;
int fa[1000001],n,m,x,y,ans,ma;
inline int find(int x){return fa[x]==x?x:find(fa[x]);}
inline void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx!=fy) fa[fx]=fy;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) fa[i]=i;
	while(m--){
		scanf("%d%d",&x,&y);
		merge(x,y);
	}
	for(int i=1;i<=n;++i){
		if(fa[i]==i) ++ans;
	}
	printf("%d",ans);
	return 0;
}

按理来说时间应该更短的,但是却超时了,本蒟蒻无法解释这个问题,各位大佬帮个忙,玄一关

2024/10/5 16:14
加载中...