代码第47行并查集数组初始化,初始化到大N这个常量,小n也会变成大N的值,换成小n或者是小n + 任何常数都正常AC,我在第30行有输出小n的代码,求解答
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
struct edge{
int from, to, val;
} e[N];
bool cmp(edge a, edge b) {
return a.val < b.val;
}
int fa[N];
int find(int x) {
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int n, m, k;
int tot = 0;
int cnt = 0, dis = 0;
bool kurscal() {
sort(e + 1, e + 1 + tot, cmp);
for(int i = 1; i <= tot; i++) {
int x = find(e[i].from), y = find(e[i].to);
if(x != y) {
fa[y] = x;
cnt++;
dis += e[i].val;
}
cout << n << ' ' << cnt << endl;
if(n - cnt == k) return 1;
}
return 0;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= m; i++) {
int x, y, l;
cin >> x >> y >> l;
e[++tot].from = x;
e[tot].to = y;
e[tot].val = l;
}
for(int i = 1; i <= N; i++) fa[i] = i;
if(kurscal()) cout << dis;
else cout << "No Answer";
return 0;
}