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";
}
}