Segmentation C++ no print messages in online compiler

Question

This is my current code:

// PRIM MST fara heap lista adiacenta

#include<bits/stdc++.h> 
using namespace std; 
# define INF 0x3f3f3f3f 

// pereche int int denumita iPair
struct Edge {
    int destination;
    int weight;
};

Edge newEdge(int destination, int weight) {
    return { destination, weight };
}

// To compare two points 
class edgeComparator
{ 
public: 
    int operator() (const Edge& e1, const Edge& e2) 
    { 
        printf("HIIIIIIIII222");
        return e1.weight > e2.weight; 
    } 
}; 

// un graf directionat cu reprezentare prin lista de adiacenta
class Graph 
{ 
    int V; // Numar de noduri

    // Lista care retine nodul si costul muchiei pentru fiecare pereche
    list< Edge > *adj; 

public: 
    Graph(int V) {
        this->V = V;
        adj = new list<Edge> [V]; 
    }; // constructorul

    // adauga o muchie grafului
    void addEdge(int from, int to, int weight){
        adj[from].push_back(newEdge(to, weight)); // http://www.cplusplus.com/reference/list/list/push_back/ pentru push back
        adj[to].push_back(newEdge(from, weight)); 
    };

    // // Printeaza drumul cel mai scurt din sursa la toate celelalte noduri
    void primMST(int numberElemOp){
        // Creaza o coada de prioritati pentru a stoca toate nodurile.
        // Sintaxa aparent o poti vedea aici http://geeksquiz.com/implement-min-heap-using-stl/ de ce e cum e
        priority_queue< Edge, vector <Edge> , edgeComparator > pq; 

        int src = 0; // Nodul 0 devine sursa
        numberElemOp += 1;

        // Creem un vector unde sa stocam cheile si le initializam cu infinit
        vector<int> key(V, INF); 

        // Pentru stocarea array-ului de parinti
        vector<int> parent(V, -1); 

        // Vector care ne arata ce noduri au fost incluse in mst
        vector<bool> inMST(V, false); 

        // Baga nodul parinte in coada de prioritati si face cheia 0
        pq.push(newEdge(0, src));
        key[src] = 0; 

        numberElemOp += 2;

        /* Pana cand coada devine vida */
        while (!pq.empty()) 
        { 

            int u = pq.top().destination; 
            pq.pop(); 

            inMST[u] = true; // Include nodul in MST

            // // i este utilizat pentru a lua toate nodurile vecine
            printf("HIIIIIIIII");
            list< Edge >::iterator i;
            printf("HIIIIIIIII");

            numberElemOp += 4;
            for (i = adj[u].begin(); i != adj[u].end(); ++i) 
            { 
                // Ia numele si costul nodului vecin cu u
                int v = (*i).destination; 
                int weight = (*i).weight; 

                // If v is not in MST and weight of (u,v) is smaller 
                // than current key of v 

                // Daca v nu este in MST si costul muchiei (u,v) este mai mic decat cheia lui v
                numberElemOp += 5;
                if (inMST[v] == false && key[v] > weight) 
                { 
                    // Updateaza cheia lui v
                    key[v] = weight; 
                    pq.push(newEdge(key[v], v)); 
                    parent[v] = u;
                    numberElemOp += 7;
                } 
            } 
        } 

        // Printeaza muchiile msg-ului
        for (int i = 1; i < V; ++i) 
            printf("%d - %d\n", parent[i], i); 

        printf("Numar operatii elementare: %d", numberElemOp);
    }
}; 

int main() 
{ 
    int numberElemOp;
    // creaza un graf
    printf("HIIIIIIIII");
    int V = 9;

    numberElemOp += 1;
    Graph g(V); 

    g.addEdge(0, 1, 4); 
    g.addEdge(0, 7, 8); 
    g.addEdge(1, 2, 8); 
    g.addEdge(1, 7, 11); 
    g.addEdge(2, 3, 7); 
    g.addEdge(2, 8, 2); 
    g.addEdge(2, 5, 4); 
    g.addEdge(3, 4, 9); 
    g.addEdge(3, 5, 14); 
    g.addEdge(4, 5, 10); 
    g.addEdge(5, 6, 2); 
    g.addEdge(6, 7, 1); 
    g.addEdge(6, 8, 6); 
    g.addEdge(7, 8, 7); 

    g.primMST(numberElemOp); 

    return 0; 
}

When I try to run it i get a segmentation fault and i don't quite understand why. The code worked in this form: https://www.geeksforgeeks.org/prims-algorithm-using-priority_queue-stl/ But now it does not anymore.

The problem is somewhere at priority queue but I can't imagine the reason...

Stop using bit/stdc++.h. We already told you so in your earlier question. Then use a debugger. — Matthieu Brucher, Nov 04 '18 at 13:44
`#include` and `using namespace std;` together is just a ticking bomb. You never know when it's going to explode in your face. — Yksisarvinen, Nov 04 '18 at 13:46
Enabling warnings could help as well: `numberElemOp is used uninitialized in this function [-Wuninitialized]` you did not assign it an initial value. — Floris Velleman, Nov 04 '18 at 13:46
`Graph` is missing a destructor to clean op `adj`. But, why are you using manual memory management in the first place? Use containers and/or smart pointers. — Jesper Juhl, Nov 04 '18 at 13:48
@MatthieuBrucher If i do that i get 100 other errors. manual because I am not allowed to use many things :D, I am constrained by a lot with mostly manual stuff — Lucian Tarna, Nov 04 '18 at 13:51
Please don't debug by iterative questioning on stackoverflow. — Passer By, Nov 04 '18 at 13:51
The first thing to do when debugging is to figure out which line of your program was the line where the crash occurred. You can do that using a debugger, or by inserting temporary debug-print statements and seeing which one was the last one to print out before the crash. Once you know *where* the crash occurred, you're more likely to understand *why* the crash occurred. — Jeremy Friesner, Nov 04 '18 at 13:57
@LucianTarna Look at this link https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h and then include the proper headers. — Matthieu Brucher, Nov 04 '18 at 14:34

score 1 · Accepted Answer · answered Nov 04 '18 at 13:53

You are accessing inMST vector out of bounds after popping elements from queue, why ?

pq.push(newEdge(key[v], v)); // push new element into queue
                ^^^^    ^^

first arg should be destination but you are passing distance, second arg should be weight but you are passing destination. Replace to:

pq.push(newEdge(v, key[v]));

Problem with uninitialized numberElemOp variable was already pointed out in comments.

Segmentation C++ no print messages in online compiler

1 Answers1