1

Добрый день!

Помогите пожалуйста или дайте подсказку. Решаю задачу. Условие следующее:

В школе перед Новым Годом устраивают игру в Тайного Санту. Каждому ученику i выдается ученик ai, которому он должен подарить подарок. Костя, как администратор игры, определил каждому школьнику свое число ai. Но потом его коллега Маша спросила: А правда ли, что если начать цепочку подарков от школьника 1 к школьнику a1, потом a1 и так далее, то цепочка замкнется на школьнике 1, после того, как задействует всех остальных учеников ровно по одному разу? Костя не знает, правда это или нет, но он собирается изменить ровно одно число a, чтобы получить конфигурацию, которая устроит Машу. Помогите ему с этим.

Формат входных данных

В первой строке находится натуральное число n — количество школьников (2≤n≤10^5). В следующей строке находится n натуральных чисел a — ученик, который достался Тайному Санте с номером i(1≤a≤n).

Формат выходных данных

В первой строке выведите два числа (1≤x,y≤n,x≠y) — номер ученика x, которому нужно изменить число ax, и новое значение ax.

Должно выполняться условие ax≠y. Если ответов несколько — выведите любой.

Если сделать это невозможно — выведите <<−1−1>> введите сюда описание изображения

Написал код ниже, но почему то проходит не все тесты. Во входной строке ориентированный граф в коде я ищу ребра у вершин которых есть больше двух ребер, если есть больше двух ребер перенаправляю на вершину у которой 0 ребер для того чтобы сделать из функционального графа цикл, если граф возможно сделать циклом то вершину которую можно заменить вывожу на экран. И я вообще я же правильно понимаю что в функциональном графа у вершины может быть два ребра одно входит другое выходит? Прошу может кто-нибудь подсказать что не так делаю с этим графом, так как я новичок нужна подсказка.

var n = int.Parse(Console.ReadLine()!);
var inputStr = Console.ReadLine()!.Split(" ", StringSplitOptions.RemoveEmptyEntries);

if (n < 2 || n > Math.Pow(10, 5)) throw new ArgumentOutOfRangeException(
    $"Argument {n} is Out Of Range. Arguments must be between 2 and 10^5.");

// Парсим строку и создаем матрицу смежности
var vertices = new int[n];

for (int i = 0; i < n; i++)
{
    var vertice = int.Parse(inputStr[i]);

    if (vertice < 0 || vertice > n) throw new ArgumentOutOfRangeException(
        $"Argument {vertice} is Out Of Range. Arguments must be between 0 and {n}.");

    vertices[i] = vertice;
}

// Создаем матрицу смежности
int[,] adjacencyMatrix = new int[n, n];

// Заполняем матрицу смежности
var sourceVertex = 0;
var destinationVertex = 0;

for (int i = 0; i < vertices.Length; i++)
{
     if (i == vertices.Length - 1)
     {
         sourceVertex = vertices[^1] - 1;
         destinationVertex = vertices[0] - 1;
     }
     else
     {
         sourceVertex = vertices[i] - 1;
         destinationVertex = vertices[i + 1] - 1;
     }

    adjacencyMatrix[sourceVertex, destinationVertex] = 1;
    adjacencyMatrix[destinationVertex, sourceVertex] = 1;
}

// Ищем вершину со степенью 0 и вершину со степенью больше двух
var desList = new List<int>();
var sourList = new List<int>();

for (int i = 0; i < n; i++)
{
    int degree = 0;

    for (int j = 0; j < n; j++)
    {
        degree += adjacencyMatrix[i, j];
    }

    if (degree == 0) sourList.Add(i + 1);
    else if (degree > 2) desList.Add(i + 1);
}

var result = sourList.Any() && desList.Any() ? $"{desList.First()} {sourList.First()}" : "-1 -1";
Console.WriteLine(result);
14
  • Матрица смежности (которая не нужна) займёт 10^10 ячеек. Это 40 гигабайт. Не думаю что на тесте хватит памяти. Commented 14 мар. 2023 в 13:25
  • @StanislavVolodarskiy Понял, учту, спасибо. Просто в подсказке писали считать количество ребер каждой вершины, поэтому я подумал то нужно матрицу смежности сделать. Commented 14 мар. 2023 в 13:31
  • Не обработан случай когда вершин с неединичными степенями много. Например: 1 1 4 4. Commented 14 мар. 2023 в 13:31
  • @StanislavVolodarskiy только об этом подумал) А во стальном все норм? Commented 14 мар. 2023 в 13:33
  • Для 2 3 1 вы ответите -1 -1. А можно ответить 1 2. Это случай когда цикл уже есть. Commented 14 мар. 2023 в 13:36

1 ответ 1

0

Можно ввести отношение > таким образом: i > ai если i-й школьник дарит подарок ai-тому школьнику. Условие решения: отношение > образует цикл, включающий всех школьников. Условие разрешимости: граф отношения выглядит как греческая буква ро ρ - то есть цикл с хвостом. Это означает, что

  • есть ровно одна компонента связности
  • есть ровно одна вершина i без входящих,
  • и есть ровно одна вершина j с двумя входящими

Так как компонента связности одна, существует путь от i к j.

Нужно найти элемент k такой, что стоит перед j в цикле, и поставить a_k = i. Тем самым компонента связности превратится в цикл.

Алгоритм получается такой:

  1. если более одной вершины с 0 входящих - ответ НЕТ
  2. если есть вершины с более чем двумя входящими - ответ НЕТ
  3. если есть более одной вершины с двумя входящими - ответ НЕТ
  4. если все вершины только с одной входящей, проверить что цикл из 1 проходит через все вершины. Если такой есть - ответ ГОТОВО, если часть вершин выпадает - ответ НЕТ
  5. к этому моменту остался только случай одна вершина с 0 входящих (максимальная) и одна вершина с 2 входящими (начало цикла). Найти путь от максимальной до начала цикла. В этом маршруте есть вершина x предшествующая началу цикла. Взять вершину y из входящих в начало цикла, такую, что x != y. Назначить a_y = максимальная. Проверить, что получившийся цикл охватывает все вершины. Если да, то ответ a_y = максимальная, если нет, то ответ НЕТ

(что-то мне подсказывает, что условия 2 и 3 следуют из 1 -- если есть ровно одна максимальная вершина, то не может быть более одной вершины с двумя входящими).

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.