Как сделать функцию, чтобы узнать, представляет ли массив непересекающихся наборов один раздел?

Question

Предположим, у меня есть дизъюнктный набор с реализацией массива, такой как this .

Рассмотрим этот массив непересекающихся множеств [0,0,3,3], который представляет следующий раздел: {0,1} {2,3}. Как видите, массив [0,0,3,3] представляет 2 класса разбиения, то есть {0,1} и {2,3}.

Теперь рассмотрим [0,0,1,2], который представляет раздел {0,1,2,3}. Массив [0,0,1,2] представляет один раздел.

Как мне сделать функцию, чтобы узнать, представляет ли массив отдельный раздел или нет. Функция вернет истину, если переданный ей массив представляет один раздел, и вернет ложь в противном случае.

Другой способ выразить это (см. здесь ), как узнать, все ли вершины находятся в одном дереве.

Приветствуется JavaScript или код Python. Actionscript является предпочтительным.

Любая помощь приветствуется.

Answer 1

Вы просто посчитаете количество корневых наборов.Это количество разделов, которые у вас есть.

В представлении непересекающихся множеств, корнями которого являются наборы, которые ссылаются на себя.Например, в [0,0,3,3] 0-> 0 и 3-> 3 являются корнями, поэтому у вас есть 2 раздела.В [0,0,1,2] только 0-> 0 является корнем, поэтому есть один раздел.

Answer 2

Один из простых способов сделать это - сохранить дополнительную информацию в структуре данных Disjoint Set Union (DSU).

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

Существует простой способ реализовать это без использования дополнительного пространства:

В уроке, который вы связали P[u], хранится родительский элемент элемента u, и в случае, если u является корнем непересекающегося множества, он сохраняет себя, так что u является корнем, если P[u] === u

В нашей модифицированной реализации мы помечаем корневые узлы отрицательными числами, поэтому u является корнем непересекающегося множества, если P[u] < 0, и теперь мы можем также сохранить размер непересекающегося множества как отрицательное число, поэтому, если P[u] >= 0, он действует как в стандартная реализация DSU, показывающая родителя некоторого узла, и, если он отрицательный, он показывает, что текущий узел является корнем, а -P[u] обозначает размер непересекающегося набора, который представляет этот корень.

Пример кода (JavaScript, используется только оптимизация сжатия пути, поэтому сложность для всех функций равна O (log N)):

const Find = (P,u) => P[u] < 0 ? u : P[u] = Find(P,P[u]);

const Union = (P,u,v) => {
	u = Find(P,u);
	v = Find(P,v);	
	if(u === v)return;
	P[u] += P[v]; //we merge 2 sets size of new set is sum of the sets we are merging
	P[v]  = u;
}

const iSSinglePartition = (P) => -P[Find(P,0)] === P.length;

const N = 5;
let P = new Array(N);
P.fill(-1); //now -P[u] represent size of disjoint set, initially all elements are disjoint so we set sizes to 1

console.log(iSSinglePartition(P));
Union(P,0,1);
console.log(iSSinglePartition(P));
Union(P,1,2);
console.log(iSSinglePartition(P));
Union(P,3,4);
console.log(iSSinglePartition(P));
Union(P,3,0);
console.log(iSSinglePartition(P));