首先这个是题目,本蒟蒻为了复习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;
}
按理来说时间应该更短的,但是却超时了,本蒟蒻无法解释这个问题,各位大佬帮个忙,玄一关