Bug in finding mininum spanning tree using Kruskal's algorithm

[lypan]

I write the minmium spanning tree using kruskal algorithm and it comes out the error with invalid read of size 4 in the (code.cpp:30). I have google it and know that it is happens when your program reads or writes memory at a place which Memcheck reckons it shouldn't.But I see the line 30 https://docs.google.com/document/d/1_AhOdDkyZGNTBVHspyGtnSQoU1tYkm0nVA5UABmKljI/edit?usp=sharing

int findset(int x){
    if(x != parent[x])parent[x] = findset(parent[x]);
    return parent[x];
}

and it indicate different with the error indicate and cannot find the problem. I think that the index X in vector Parent should be good because I use the maximum to record the largest element

if(u > maximum)maximum = u;
if(v > maximum)maximum = v;

and use it to initialize all before element in the vector Parent.

for(int i = 0; i <= maximum; i ++)parent.push_back(i);
The following code is called by like

CreateNewGraph(); AddEdge(1, 2, 10); AddEdge(2, 4, 10); AddEdge(1, 3, 100); AddEdge(3, 4, 10); GetMST(mst_edges);

and the result will be (1,2) (2,4) (3,4).

and call UpdateEdge(1, 3, 0.1); GetMST(mst_edges); and the result will be (1,2) (1,3) (2,4).

It is sent to a system to execute and it will be called like above but in a lot of time cycle above.

#include <vector>
#include <utility>
#include <algorithm>

using namespace std;


namespace HOMEWORK{
    int maximum = 0;
    class Edge{
        public:
            Edge(unsigned int, unsigned int, double);
            unsigned int u;
            unsigned int v;
            double w;
        friend bool operator<(const Edge& a, const Edge& b){
         return a.w < b.w;
        }
    };
    Edge::Edge(unsigned int source = 0, unsigned int destination = 0, double weight = 0.0){
        u = source;
        v = destination;
        w = weight;
    }

    vector<Edge> graph(0);
    vector<int> parent(0);

    int findset(int x){
        if(maximum + 1 > x){
            if(x != parent[x])parent[x] = findset(parent[x]);
        }
        return parent[x];
    }

    void CreateNewGraph(){
        graph.clear();
        parent.clear();
        maximum = 0;
    }

    void AddEdge(unsigned int u, unsigned int v, double w){
        graph.push_back(Edge(u,v,w));
        if(u > maximum)maximum = u;
        if(v > maximum)maximum = v;
    }

    void UpdateEdge(unsigned int u, unsigned int v, double w){
        for(int i = 0; i < graph.size(); i ++){
            if(graph[i].u == u && graph[i].v == v)graph[i] = Edge(u,v,w);
        }
    }

    void GetMST(vector<pair<unsigned int, unsigned int> >& mst_edges){
        mst_edges.clear();
        parent.clear();
        int e = graph.size();
        parent.resize(maximum + 1);
        for(int i = 0; i <= maximum; i ++)parent.push_back(i);
        stable_sort(graph.begin(), graph.end());
        for(int i = 0; i < e; i ++){
            //cout << graph[i].u << ":" << graph[i].v << ":" << graph[i].w << ":" << parent[i + 1] << endl;
            int pu = findset(graph[i].u);
            int pv = findset(graph[i].v);
            if(pu != pv){
                parent[pu] = parent[pv];
                mst_edges.push_back(make_pair(graph[i].u, graph[i].v));
            }
        }
    }

    void Init(){
    }

    void Cleanup(){
    }


}