Почему возникает segmentation fault?

144
24 июля 2019, 12:50

Прохожу данное задание в курсе на Степике:
https://stepik.org/lesson/41560/step/4?discussion=821732&unit=20013

Условие:

Мой код:

    #include  <iostream>  
    #include <vector>  
    #include <algorithm>  
    using vector = std::vector<size_t>;  
int find(size_t i, vector& parent)
{
    while(i != parent[i])
        i = parent[i];
    return i;
}
void union_sets(size_t i, size_t j, vector& parent, vector& rank)
{
    int i_id = find(i, parent);
    int j_id = find(j, parent);
    if(i_id == j_id)
    return;
    if(rank[i_id] > rank[j_id])
        parent[j_id] = i_id;
    else
        parent[i_id] = j_id;
    if(rank[i_id] == rank[j_id])
        rank[j_id] += 1;
}
int main()
{
    size_t flag = 1;
    size_t n = 0;
    size_t e = 0;
    size_t d = 0;
    std::cin >> n;
    std::cin >> e;
    std::cin >> d;
    vector parent(n + 1);
    for(size_t i = 1; i < parent.size(); i++)
        parent[i] = i;
    vector rank(e + 1);
    for(size_t i = 1; i < rank.size(); i++)
        rank[i] = 1;
    for(size_t i = 0; i < e; i++)
    {
        size_t first = 0;
        size_t second = 0;
        std::cin >> first;
        std::cin >> second;
        union_sets(first, second, parent, rank);
    }
    for(size_t i = 0; i < d; i++)
    {
        size_t first = 0;
        size_t second = 0;
        std::cin >> first;
        std::cin >> second;
        size_t i_id = find(first, parent);
        size_t j_id = find(second, parent);
        if(i_id == j_id)
        flag = 0;
    }
    std::cout << flag << " ";
    return 0;
}

На 47 тесте происходит ошибка:
Failed test #47. Runtime error Segmentation fault (core dumped)

Все тесты из условия проходят. В чем может быть проблема? Спасибо.

Answer 1

Почему у вас размер массива rank вдруг установлен в e + 1? Он ведь должен иметь тот же размер, что и parent, т.е. n + 1. Очевидно, вы вылетаете за пределы rank, что и приводит к segmentation fault.

В остальном все выглядит нормально, хоть и местами нелогично. Удивляет неоправданная мешанина из size_t и int. Формально диапазона типа int может быть недостаточно для представления значений порядка 105. Также непонятно почему parent передается в find по значению.

READ ALSO
Как найти число, которое встречается во всех строках матрицы?

Как найти число, которое встречается во всех строках матрицы?

Задан целочисленный массив N*M (N - количество строк, M - столбцов)Каждая строка массива упорядочена по возрастанию

153
node-ffi - Передать указатель на строку в dll

node-ffi - Передать указатель на строку в dll

В dll определена функция:

155
Способы хранения данных в С++

Способы хранения данных в С++

На каникулы задали лабораторную работу (сделать программу, которая будет хранить метаданные файла, и текст содержащийся в нем, и различные...

166