Использование parents[find(i)] = j
позволяет значению стать меньше его индекса, повторяя значение, которым могут стать индексы.Это может привести к ситуации, когда 2 элемента имеют обратные индексы / значения друг друга.Например:
Учитывая A.length == 5
, ваш начальный массив будет выглядеть следующим образом:
parent [0] = 0;родители [1] = 1;родители [2] = 2;родители [3] = 3;parent [4] = 4;
Значения, которые мы используем, будут для similar
, возвращающими true.Начиная с i = 2, j = 1
, вызовы будут:
find(2); //Array doesn't change in recursive function
//Resulting array after applying j to parents[2]:
// parents[0] = 0; parents[1] = 1; parents[2] = 1; parents[3] = 3; parents[4] = 4;
Далее, i = 3, j = 1
:
find(3); //Array doesn't change in recursive function
//Resulting array after applying j to parents[3]:
// parents[0] = 0; parents[1] = 1; parents[2] = 1; parents[3] = 1; parents[4] = 4;
Затем i = 3, j = 2
:
find(3); find(1); //Array doesn't change in recursive function
//Resulting array after applying j to parents[1]:
// parents[0] = 0; parents[1] = 2; parents[2] = 1; parents[3] = 1; parents[4] = 4;
Теперь вы можете видеть, что у нас настроен бесконечный цикл (parents[1] = 2; parents[2] = 1
).Если find
вызывается с 1 или 2, это застрянет между этими двумя значениями.Нам нужно еще два шага, чтобы добраться туда.i = 4, j = 1
:
find(4); //Array doesn't change in recursive function
//Resulting array after applying j to parents[1]:
// parents[0] = 0; parents[1] = 2; parents[2] = 1; parents[3] = 1; parents[4] = 1;
Наконец, i = 4, j = 2
:
find(4); find(1); find(2); find(1); find(2); find(1); find(2); ...
Использование parents[find(j)] = i
означает, что назначенное значение не может стать ниже, поскольку i
всегдаувеличивается, тогда как j
повторяется для каждой итерации i
.j
может быть любым значением 0 to i -1
.