Segmentation C++ no print messages in online compiler

3136 views c++
8

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...

answered question

Stop using bit/stdc++.h. We already told you so in your earlier question. Then use a debugger.

#include<bits/stdc++.h> and using namespace std; together is just a ticking bomb. You never know when it's going to explode in your face.

Enabling warnings could help as well: numberElemOp is used uninitialized in this function [-Wuninitialized] you did not assign it an initial value.

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.

@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

Please don't debug by iterative questioning on stackoverflow.

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.

1 Answer

5

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.

posted this

Have an answer?

JD

Please login first before posting an answer.