Добрый день!
Помогите пожалуйста или дайте подсказку. Решаю задачу. Условие следующее:
В школе перед Новым Годом устраивают игру в Тайного Санту. Каждому ученику 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);
1 1 4 4
.2 3 1
вы ответите-1 -1
. А можно ответить1 2
. Это случай когда цикл уже есть.