Problema minimum spanning tree 70/100

Ciao a tutti, sto utilizzando Kruskal e union-find per risolvere il problema minimum spanning tree.
Tuttavia il codice implementato non risolve tutti i casi di test, ottenendo un punteggio di 70/100. Potreste aiutarmi a trovare il problema?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
	int a;
	int b;
	long long int w;
	Edge() :  a(0), b(0), w(0) {};

};
long long int tsize;
vector<int> link; // representative for element x
vector<int> sizee; // sizee[i] == size of the set where is the element
bool comp(Edge &a, Edge &b) {
	return a.w<b.w;
}

int findd(int xx) { // returns the representative for element x
	while(xx != link[xx]) {
		xx=link[xx];
	}
	return xx;
}
bool same(int a, int b) { // checks if a and b are in the same set
	return findd(a) == findd(b);
}
void unite(int a, int b) { // joins two sets
	a=findd(a);
	b=findd(b);
	if(sizee[a]<sizee[b]) swap(a,b);
	sizee[a]+=sizee[b];
	link[b]=a;
}
int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	tsize=0;
	int N, M;
	cin>>N>>M;
	link.resize(N);
	sizee.assign(N, 1);
	vector<Edge> ed(M);
	vector<Edge> res;
	for(int i=0;i<M;i++) {
		Edge ted;
		cin>>ted.a;
		cin>>ted.b;
		cin>>ted.w;
		ed[i] = ted;
	}
	sort(ed.begin(), ed.end(), comp);
	for(int i=0;i<N;i++) {
		link[i] = i;
	}
	
	for(int i=0;i<M;i++) {
		if(!same(ed[i].a, ed[i].b)) {
			unite(ed[i].a, ed[i].b);
			tsize+=ed[i].w;
			res.push_back(ed[i]);
		}
	}
	cout<<tsize<<"\n";
	for(int i=0;i<res.size();i++) {
		cout<<res[i].a<<" "<<res[i].b<<"\n";
	}
}

Ciao, il codice e’ corretto ma stai sempre lavorando con nodi indicizzati a partire da 1
Di conseguenza quando vai a prendere il n-esimo elemento di un array non lo stai prendendo con indice n-1, bensi’ n
Essendo i tuoi di vettori di dimensione n, questo li fa andare out of range, sballando i calcoli
Per fare 100 e’ sufficiente fare il resize dei vettori a n+1

1 Mi Piace