Im getting SIGABRT error in my c++ recursive code

Question

Im running this code and im getting this error

Fatal glibc error: malloc.c:2593 (sysmalloc): assertion failed: (old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)
Aborted (core dumped)

When i run it using gdb it says this:

Fatal glibc error: malloc.c:2593 (sysmalloc): assertion failed: (old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)

Program received signal SIGABRT, Aborted.
__pthread_kill_implementation (threadid=<optimized out>, signo=signo@entry=6, no_tid=no_tid@entry=0) at pthread_kill.c:44
44            return INTERNAL_SYSCALL_ERROR_P (ret) ? INTERNAL_SYSCALL_ERRNO (ret) : 0;

I have no idea why. Please help me.

The code:

#include <bits/stdc++.h>
using namespace std;

bool cancolor(vector<vector<int>> &mat, int m, vector<int> colors, int idx)
{
    if (idx == mat.size())
    {
        return true;
    }
    else
    {
        int color = 1;
        while (color <= m)
        {
            int edges = 0;
            int i = 0;
            while (i < mat.size())
            {
                if (mat[idx][i] == 1)
                {
                    edges++;
                    if (colors[i] != color)
                    {
                        colors[idx] = color;
                        if (cancolor(mat, m, colors, idx + 1))
                        {
                            return true;
                        }
                        colors[idx] = 0;
                    }
                    else
                    {
                        i = mat.size();
                    }
                }
                i++;
            }
            if (edges == 0)
            {
                colors[idx] = color;
                if (cancolor(mat, m, colors, idx + 1))
                {
                    return true;
                }
                return false;
            }
            color++;
        }
        return false;
    }
}

string graphColoring(vector<vector<int>> &mat, int m)
{
    vector<int> colors;
    for (int i = 0; i <= m; i++)
    {
        colors.push_back(0);
    }
    if (cancolor(mat, m, colors, 0))
    {
        return "YES";
    }
    return "NO";
}

int main()
{
    vector<vector<int>> mat = {{0, 0, 0, 1, 0, 0, 0},
                               {0, 0, 1, 0, 1, 0, 0},
                               {0, 1, 0, 0, 1, 0, 1},
                               {1, 0, 0, 0, 0, 0, 0},
                               {0, 1, 1, 0, 0, 0, 0},
                               {0, 0, 0, 0, 0, 0, 0},
                               {0, 0, 1, 0, 0, 0, 0}};
    cout << graphColoring(mat, 5) << endl;
    return 0;
}

If youre wondering what im trying to acheive with this, here is the link: https://www.codingninjas.com/codestudio/problems/981273

I tried to run it using pythontutor but it ended after 174 steps or so, after 5th node.

Answer 1

The problem is in graphColoring; m is the number of colors, but your colors vector should have mat.size() elements.
Writing outside that vector (as you do) has undefined behaviour, and likely leads to some type of memory corrution.