Прохожу данное задание в курсе на Степике:
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)
Все тесты из условия проходят. В чем может быть проблема? Спасибо.
Почему у вас размер массива rank
вдруг установлен в e + 1
? Он ведь должен иметь тот же размер, что и parent
, т.е. n + 1
. Очевидно, вы вылетаете за пределы rank
, что и приводит к segmentation fault.
В остальном все выглядит нормально, хоть и местами нелогично. Удивляет неоправданная мешанина из size_t
и int
. Формально диапазона типа int
может быть недостаточно для представления значений порядка 105. Также непонятно почему parent
передается в find
по значению.
Виртуальный выделенный сервер (VDS) становится отличным выбором
Задан целочисленный массив N*M (N - количество строк, M - столбцов)Каждая строка массива упорядочена по возрастанию
На каникулы задали лабораторную работу (сделать программу, которая будет хранить метаданные файла, и текст содержащийся в нем, и различные...