Почему может быть ошибка во время компиляции?

Question

[impelix]

У меня есть написанный алгоритм Краскала(судя по всему криво) и есть задача.
Почему-то крашится 4 теста. С ошибкой.
Где тут может быть ошибка во время выполнения программы ума не приложу.

Код

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int x, y, cost;
};

vector<int> parent, glub;

int findMN(int num){ //Ищем множество в котором находится вершина
    if (num == parent[num]) {
        return num;
    }
    return parent[num] = findMN(parent[num]);
}

int ob(int x, int y) {
    x = findMN(x);
    y = findMN(y);
    if (x == y) {
        return 0;
    }
    if (glub[x] < glub[y]) {
        swap(x, y);
    }
    parent[y] = x;
    if (glub[x] == glub[y]) {
        glub[x]++;
    }
    return 1;
}

int comp(Edge a, Edge b) {
    return a.cost < b.cost;
}

int main() {
    int n, m;
    cin >> n >> m;
    parent.resize(++n);
    glub.resize(n);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        //glub[i] = 0;
    }
    vector<Edge> g(m);
    for (int i = 0; i < m; i++) {
        cin >> g[i].x >> g[i].y >> g[i].cost;
    }

    sort(g.begin(), g.end(), comp);

    int ans = 0;
    for (int i = 0; i < m; i++) {
        if (ob(g[i].x, g[i].y)) {
            ans += g[i].cost;
        }
    }

    cout << ans;
    return 0;
}

Задача

ссылка
Требуется найти в связном неориентированном графе остовное дерево минимального веса.

Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество вершин и ребер графа соответственно (1 ≤ N ≤ 20 000, 0 ≤ M ≤ 100 000). Следующие M строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами Bi, Ei и Wi – номера концов ребра и его вес соответственно (1 ≤ Bi, Ei ≤ N, 0 ≤ Wi ≤ 100 000).

Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – вес минимального остовного дерева.

Также есть 2 вариант кода, он уже заходит на 13/15 но крашится на тех же тестах с ошибкой.

Код №2

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int x, y, cost;
};
int comp(Edge a, Edge b) {
    return a.cost < b.cost;
}

vector<int> parent, depth;

int findMN(int num){ //рекурсивно ищем множество
    if (num == parent[num]) {
        return num;
    }
    return parent[num] = findMN(parent[num]);
}

bool check(int x, int y) { //ищем предков и находим их после чего проверяем на циклы и добавляем
    x = findMN(x);
    y = findMN(y);
    if (x == y) { //если они из одного множества нам такие не нужны
        return 0;
    }
    parent[y] = x;
    return 1;
}

int main(){
    int n, m, ans = 0;
    cin >> n >> m;
    vector<Edge> g(m);
    parent.resize(++n);
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }
    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        cin >> x >> y >> cost;
        g[i].x = x;
        g[i].y = y;
        g[i].cost = cost;
    }
    sort(g.begin(), g.end(), comp);
    for (int i = 0; i < m; i++) {
        if (check(g[i].x, g[i].y)) {
            ans += g[i].cost;
        }
    }
    cout << ans;
    return 0;
}

Он проще, но тоже не заходит

Comments

[Dmitrii]

Логично было бы приложить примеры тестов с которыми работает, а с какими нет.
Также, я бы предложил начать с самых простых тестов, элементарнейших и добавить в программу логгирование, иначе не сможете понять где же все падает.
А также код ошибки, если он имеется.

[impelix]

Dmitrii, проблема в том что кода ошибки нету(компилятор просто падает и все)+ закрытая тест система

Answer 1

[Wataru]

Проблема вот тут:

parent.resize(++n);
glub.resize(n);
for (int i = 1; i <= n; i++) {

Выход за границу массива. Неопределенное поведение.
Вы выделяете массивы длины n (увеличенного на 1) и потом проходитесь от 1 до n (увеличенного на 1). Но ведь индексы в массиве только до n-1.

Правильно так:

parent.resize(n+1);
glub.resize(n+1);
for (int i = 1; i <= n; i++) {

Comments

[Anton F]

Тут больше ошибок. И увеличение длины массива выглядит не совсем корректным.
На данный момент не инициализируется нулевой элемент. Индексы с 1, а в функции ob используется с 0. Таким образом будет UB.
Можно оставить
parent.resize(++n);
glub.resize(n);
Но цикл должен быть i=0; i < n

[Wataru]

Anton F, glob - vector. Он всегда инициализирует элементы.

[Anton F]

Чем? Конструктором по умолчанию. Какие значение подставляется в int? Правильно, неизвестно какие. Или зависит от реализации, процессора, архитектура и как там флаги компиляции выставлены.
Мой комментарий больше про то, что нулевой элемент используется, но не заполняется. По коду не нашел, что он используется как-то иначе.

[Wataru]

Anton F

> Какие значение подставляется в int?

Ноль, вообще-то. Согласно стандарту - на любой архитектуре и с любыми флагами.

Читайте вот тут. Пункт 4:

The effects of value initialization are: ... 4) otherwise, the object is zero-initialized.

Value-initialization просиходит, потому что так работает vector::resize (Читайте Note в конце, ну или почитайте про default-insertion).

[Wataru]

Anton F, Ну и в дополнение, раз уж вы спорить собрались:

Можно оставить
parent.resize(++n);
glub.resize(n);

Концептуально - это неправильно. Что тут означет n? Количество вершин+1? Количество элементов в векторе (при неиспользуемом индексе 0). Костыль же.

Answer 2

[OpenAI]

Вы не инициализировали glub (вектор высоты дерева).

Просто добавьте glub[i] = 0; в цикл инициализации. Это должно исправить ошибку

Здесь исправленный код:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int x, y, cost;
};

vector<int> parent, glub;

int findMN(int num){ //Ищем множество в котором находится вершина
    if (num == parent[num]) {
        return num;
    }
    return parent[num] = findMN(parent[num]);
}

int ob(int x, int y) {
    x = findMN(x);
    y = findMN(y);
    if (x == y) {
        return 0;
    }
    if (glub[x] < glub[y]) {
        swap(x, y);
    }
    parent[y] = x;
    if (glub[x] == glub[y]) {
        glub[x]++;
    }
    return 1;
}

int comp(Edge a, Edge b) {
    return a.cost < b.cost;
}

int main() {
    int n, m;
    cin >> n >> m;
    parent.resize(++n);
    glub.resize(n);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        glub[i] = 0;
    }
    vector<Edge> g(m);
    for (int i = 0; i < m; i++) {
        cin >> g[i].x >> g[i].y >> g[i].cost;
    }

    sort(g.begin(), g.end(), comp);

    int ans = 0;
    for (int i = 0; i < m; i++) {
        if (ob(g[i].x, g[i].y)) {
            ans += g[i].cost;
        }
    }

    cout << ans;
    return 0;
}

Comments

[impelix]

не работает все равно

[OpenAI]

impelix, Ошибка изменилась?

[Wataru]

OpenAI, Инициализировать glub отдельно не надо - это же vector. Он итак инициализируется.

[OpenAI]

Точно, вы правы, а из-за чего тогда может быть данная ошибка?

[Wataru]

OpenAI, Смотрите мой ответ ниже.

[mayton2019]

Тут как-то зрение задерживается. Может переписать по другому?
return parent[num] = findMN(parent[num]);

[impelix]

mayton2019, здесь я ищу начальную точку множества, и если 2 ух ребер они((точки начаал множества, а следовательно и сами множества) одинаковы нам их нет смысла добавлять

[Евгений Шатунов]

impelix, тебе ведь не описать эту строку предложили, а сделать этот код более понятным. Сейчас код в этой строке вызывает вопросы.
Оператор присвоения возвращает результат присвоения. Это то поведение, которого ты ожидаешь от кода? Оно не всегда является очевидным.
Почему бы не переписать эту строку так?

parent[num] = findMN(parent[num]);
return parent[num];

И не стоит опасаться за двойную индексацию. Оптимизатор C++ такие места видит лучше тебя и оптимизирует полностью самостоятельно. Особенно-то при том, что изначально ты итак все сделал через двойную индексацию.