I looked through other similar questions but couldn't figure out the reason for this error. I'm writing a C++ program to implement Kruskal's Minimum Spanning Tree algorithm using Union by rank with path compression. It prints the edges of the MST correctly but including the path compression portion leads to this error:
* Error in `./kruskal': free(): invalid pointer: 0x0000000001650d00 *
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, pair<int,int> > pip;
typedef pair<int,int> pii;
class UnionFind {
vector <int> parent,rank;
public:
UnionFind(int n){
parent.resize(n);
rank.resize(n);
for (int i=0;i<n;i++) { //initialize all parents and ranks
parent[i]=i;
rank[i]=0;
}
}
int find (int x){
int root=x,y;
while (parent[root]!=root) {
root=parent[root];
}
//uncommenting the following loop gives the error
/*while (parent[x]!=root){ //path compression
y=parent[x];
parent[x]=root;
x=y;
}*/
return root;
}
void unite (int x,int y) {
x=find(x);
y=find(y);
if (rank[x]>=rank[y]){
parent[y]=x;
if (rank[x]==rank[y])
rank[x]++;
}
else parent[x]=y;
}
};
int main() {
int v1,v2,w,n,m;
cout<<"Enter number of vertices, edges: ";
cin>>n>>m;
vector <pip> edges(m);
UnionFind uf(n);
cout<<"Enter edges in the form v1,v2,w: ";//w=length of edge
for (int i=0;i<m;i++) {
cin>>v1>>v2>>w;
edges[i]=pip(w,pii(v1,v2));
}
sort (edges.begin(),edges.end()); //sort edges in increasing order or lengths
cout<<"MST: edges \n";
for (int i=0;i<m;i++){
if (uf.find(edges[i].second.first)!=uf.find(edges[i].second.second)) {
uf.unite (edges[i].second.first,edges[i].second.second);
cout<<edges[i].second.first<<"--"<<edges[i].second.second<<endl;
}
}
return 0;
}
By looking at gdb's backtrace it appears to be a problem with the vector/class destructor:
(gdb) backtrace
#0 0x00007ffff74ab267 in __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:55
#1 0x00007ffff74aceca in __GI_abort () at abort.c:89
#2 0x00007ffff74eebf3 in __libc_message (do_abort=do_abort@entry=1,
fmt=fmt@entry=0x7ffff7607168 "*** Error in `%s': %s: 0x%s ***\n")
at ../sysdeps/posix/libc_fatal.c:175
#3 0x00007ffff74f6c09 in malloc_printerr (ptr=<optimized out>,
str=0x7ffff76032ba "free(): invalid pointer", action=1) at malloc.c:4965
#4 _int_free (av=<optimized out>, p=<optimized out>, have_lock=0) at malloc.c:3834
#5 0x00007ffff74fa83c in __GI___libc_free (mem=<optimized out>) at malloc.c:2950
#6 0x0000000000402cfc in __gnu_cxx::new_allocator<int>::deallocate (this=0x7fffffffdf58,
__p=0x618d00) at /usr/include/c++/5/ext/new_allocator.h:110
#7 0x0000000000402588 in __gnu_cxx::__alloc_traits<std::allocator<int> >::deallocate (__a=...,
__p=0x618d00, __n=10) at /usr/include/c++/5/ext/alloc_traits.h:185
#8 0x0000000000401ce6 in std::_Vector_base<int, std::allocator<int> >::_M_deallocate (
this=0x7fffffffdf58, __p=0x618d00, __n=10) at /usr/include/c++/5/bits/stl_vector.h:178
#9 0x00000000004018a8 in std::_Vector_base<int, std::allocator<int> >::~_Vector_base (
this=0x7fffffffdf58, __in_chrg=<optimized out>) at /usr/include/c++/5/bits/stl_vector.h:160
#10 0x0000000000401498 in std::vector<int, std::allocator<int> >::~vector (this=0x7fffffffdf58,
__in_chrg=<optimized out>) at /usr/include/c++/5/bits/stl_vector.h:425
#11 0x000000000040140b in UnionFind::~UnionFind (this=0x7fffffffdf40, __in_chrg=<optimized out>)
at kruskal.cpp:7
#12 0x0000000000401023 in main () at kruskal.cpp:47
Could someone please explain what breaks when I include the path compression while loop?
edit: Sample input that gives the error:
10 14
1 5 1
1 8 10
2 3 2
4 1 4
4 8 1
5 6 3
6 2 1
6 3 3
6 7 7
6 9 1
8 5 5
8 9 9
9 10 2
10 7 1
There are only 10 nodes, but there are 9-10 edge and 10-7 edge, so you accessed out-of-range of the vector. Try converting the 1-origin input to 0-origin before storeing.
Try
for (int i=0;i<m;i++) {
cin>>v1>>v2>>w;
edges[i]=pip(w,pii(v1-1,v2-1));
}
instead of
for (int i=0;i<m;i++) {
cin>>v1>>v2>>w;
edges[i]=pip(w,pii(v1,v2));
}
and
cout<<(edges[i].second.first+1)<<"--"<<(edges[i].second.second+1)<<endl;
instead of
cout<<edges[i].second.first<<"--"<<edges[i].second.second<<endl;