If you write out the value of t at the top of the test-case loop, you’ll see some very unexpected values. So you’ve definitely got some corruption going on, but I’ve not been able to find out where.
I suspect there may be something wrong the the way the edges are added to the list, but I’ve not used C++ in earnest for a very long time, and my memory is getting hazy.
I’m thinking that temp goes out of scope when the loop ends, and so the memory in the edge list will be deallocated and can be reused. The list of edges always looks ok when I’ve printed it, but the loop to find the MST only ever examines the first edge.
I tried changing edge to be a struct, because then it’s a value type and not a reference, but it made no apparent difference. I also tried pre-sizing the edge list (like you do for the parent and rank arrays), but again, no difference.
I also discovered that if you comment out the call to union_e, the corruption doesn’t seem to happen, but I can’t see anything wrong with union_e. I think this is probably because this leaves the edge list un-overwritten.