MAXimal

���������: 11 Jun 2008 10:56
�������������: 24 Jan 2013 12:47

���������� [������]

������� ���������������� ��������

� ������ ������ ��������������� ��������� ������ "������� ���������������� ��������" (�� ���������� "disjoint-set-union", ��� ������ "DSU").

��� ��������� ������ ������������� ��������� �����������. ���������� ������� ��������� ���������, ������ �� ������� ��������� � ��������� (���� �����������) ���������. �� ���� �������� ����� ���������� ��� �����-���� ���������, � ����� ����� ���������, � ����� ��������� ������ ��������� ��������� �������. �����, � ������������ ��������, �������� ��� ���� �������� — �������� ������ ��������, ������� ���������� � ��������� ���������.

����� �������, ������� ��������� ������ ��������� ������ ������� ����� �� ��� ��������:

  • {\rm make\_set}(x) — ��������� ����� ������� x, ������� ��� � ����� ���������, ��������� �� ������ ����.

  • {\rm union\_sets}(x,y) — ���������� ��� ��������� ��������� (���������, � ������� ��������� ������� x, � ���������, � ������� ��������� ������� y).

  • {\rm find\_set}(x) — ����������, � ����� ��������� ��������� ��������� ������� x. �� ����� ���� ��� ���� ������������ ���� �� ��������� ��������� (���������� �������������� ��� ������� (� ������������ ���������� "leader")). ���� ������������� ���������� � ������ ��������� ����� ���������� ������ (� ����� �������� � �������� �������, � ������, ����� ������� {\rm union\_sets}()).

    ��������, ���� ����� {\rm find\_set}() ��� �����-�� ���� ��������� ������ ���� � �� �� ��������, �� ��� ��������, ��� ��� �������� ��������� � ����� � ��� �� ���������, � � ��������� ������ — � ������ ����������.

����������� ���� ��������� ������ ��������� ������ ������ �� ���� �������� ����� �� O(1) � ������� (����� �������� �� ����������� ��. ���� ����� �������� ���������).

����� � ����� �� ����������� ������ ������ �������������� ������� ���������� DSU, ����������� �������� ����������� O(\log n) � ������� �� ���� ������ ��� m \ge n; � ��� m >> n (�.�. m ����������� ������ n) — � ����� ������� O(1) � ������� �� ������ (��. "�������� DSU � ���� ������ ������ ��������").

���������� ����������� ��������� ������

����������� �������, � ����� ���� �� ����� ������� ��� ����������.

��������� ��������� �� ����� ������� � ���� ��������: ���� ������ ������������� ������ ���������. ������ ������ — ��� ������������� (�����) ���������.

��� ���������� ��� ��������, ��� �� ������� ������ {\rm parent}, � ������� ��� ������� �������� �� ������ ������ �� ��� ������ � ������. ��� ������ �������� ����� �������, ��� �� ������ — ��� ���� (�.�. ������ ������������� � ���� �����).

������� ����������

�� ��� ����� �������� ������ ���������� ������� ���������������� ��������. ��� ����� �������� �������������, �� ����� �� ������� � � ������� ���� ������, ������� � ����� ����� ����������� ����� ������.

����, ��� ���������� � ���������� ��������� �������� � ��� � ������� ������� {\rm parent}.

����� ������� ����� ������� (�������� {\rm make\_set}(v)), �� ������ ������ ������ � ������ � ������� v, �������, ��� � ������ — ��� ��� ����.

����� ���������� ��� ��������� (�������� {\rm union\_sets}(a,b)), �� ������� ����� ������� ���������, � ������� ��������� a, � ���������, � ������� ��������� b. ���� ������ �������, �� ������ �� ������ — ��� ������, ��� ��������� � ��� ��� ���� ����������. � ��������� ������ ����� ������ �������, ��� ������ ������� b ����� a (��� ��������) — ��� ����� ����������� ���� ������ � �������.

�������, ���������� �������� ������ ������ ({\rm find\_set}(v)) ������: �� ����������� �� ������� �� ������� v, ���� �� ����� �� �����, �.�. ���� ������ �� ������ �� ���� � ����. ��� �������� ������� ����������� ���������� (�������� ��� ����� ������ �����, � ����� � ������������ �������������).

void make_set (int v) {
	parent[v] = v;
}
 
int find_set (int v) {
	if (v == parent[v])
		return v;
	return find_set (parent[v]);
}
 
void union_sets (int a, int b) {
	a = find_set (a);
	b = find_set (b);
	if (a != b)
		parent[b] = a;
}

�������, ����� ���������� ������� ���������������� �������� ������ ������������. ����� ��������� ������, ����� ����� ���������� ����������� �������� ��������� ��������, ��� ��������� — ��� ������, ������������ � ������� �������. � ���������� ������ ����� {\rm find\_set}() ����� �������� �� ����� ����� �� ����� ������� ������� ������, �.�. �� O(n).

��� ������ ������ �� ��� �����������, ������� �� ���������� �������� (����������� ����� ������). ������� ���������� ��� �����������, ������� �������� (���� ����������� �� �����������) ����������� �������� ������.

��������� ������ ����

��� ��������� ������������� ��� ��������� ������ {\rm find\_set}().

��� ����������� � ���, ��� ����� ����� ������ {\rm find\_set}(v) �� ����� �������� ������ p ���������, �� ��������, ��� � ������� v � ���� ���������� �� ���� ������ — ������ ���� ����� p. ����� ����� ��� �������, ������������ �� {\rm parent}[] �� ��� ������� p.

����� �������, � ������� ������� {\rm parent}[] ����� ��������� ��������: ������ ��� ������ ������ �������, �.�. ��� ������ ������� ��� ����� ��������� �� ���������������� ������, � ������ ������, ������ ������ ������, � �.�.

� ������ �������, �������, ��� ������ �������, ����� ��� ��������� {\rm parent} ������ ��������� �� ������: ����� ��� ���������� �������� {\rm union\_sets}() �������� �� ��������� ������� � O(n) ���������.

����� �������, � ������� {\rm parent}[] ������� ��������� ������ ��� � ������� �������, ��������, �������� �������.

����� ���������� �������� {\rm find\_set}() �������� ��������� �������:

int find_set (int v) {
	if (v == parent[v])
		return v;
	return parent[v] = find_set (parent[v]);
}

����� ������� ���������� ������ ��, ��� ������������: ������� ���� ����������� ������� ��������� ������ ���������, � �����, � �������� ��������� �����, ���� ����� ������������� ������� {\rm parent} ��� ���� ���������� ���������.

����������� ��� �������� ����� � ������������, �� ����� ������� ������������ ��� ������� �� ������: ������ ����� �������� ������, ������ — ��������� ��� ���� �������� ����. �������, �� �������� ������������� ���������� �� ��� ������������� ��������.

������ ����������� ��� ���������� ��������� ������ ����

�������, ��� ���������� ����� ��������� ������ ���� ��������� ������� ��������������� �����������: O(\log n) �� ���� ������ � �������.

�������, ���, ��������� �������� {\rm union\_sets}() ������������ �� ���� ��� ������ �������� {\rm find\_set}() � ��� O(1) ��������, �� �� ����� ��������������� � �������������� ������ �� ������ ������� ������ O(m) �������� {\rm find\_set}().

������ ����� w[v] ������� v ����� �������� ���� ������� (������� � ����). ���� ������, ��������, ����� ������ ������������� � �������� ������ ���������.

������ �������� ����� (a,b) �������� ����� ������ ����� �����: |w[a] - w[b]| (��������, � �������-������ ��� ������ ������, ��� � �������-�������). ����� ��������, ��� ������ ������-���� �������������� ����� (a,b) ����� ������ ������������� � �������� ������ ���������.

����� ����, �������� ���� �� ������: ����� ��������, ��� ����� ����� ����� k, ���� ��� ������ ����������� ������� [2^k; 2^{k+1}-1]. ����� �������, ����� ����� — ��� ����� �� 0 �� \lceil \log n \rceil.

����������� ������ ������������ ������� x � ����� �������, ��� �������� ����� � � ������: ������� ��� ����������� (���� ������� x �������� �������), ����� ���������� ����� �� x � �����-�� ������� (����� ��������� � �������� x �������������� � ������� ���������), � ����� ����� �������� ��� ������ ����� � �������� ������� {\rm find\_path}. �������, ��� ��� ���������� ����������� ������ ���������� ������ (��� ������ �����): ��� ��������� ������ ������� O(1) ������� �� ���� ������.

���������� ������ ���������� ������ �������� {\rm find\_set}: �� �������� � ������ ����� ���������� ����, ������ ��� ���� ����� ���� � ������������� �� � ������.

���������� ���� ���� � �������� �� ������������ ��������� ����� ������� ������ (�.�. �� ����� ��� �� ������ ����� �� ������ 0, 1, \ldots \lceil \log n \rceil). ��� ����� �� ��������� O(\log n) ���� �� ������� �������.

���������� ������ ��� ��������� ���� ����� ����. ��� ������� ������ �����, ���� ��� ����� ����� k, ����������, ��� � ���� ���� ���� ��� ���� ����� ������ k (����� �� ���� �� ������� ��������� ������� �����, ��� ������������� ������������� ������ k). ����� �������, ����� ������ ���� ��� ����� ��������� �� ����� ������ ��� ������� k+1. ��������, ��� ����������� ��� ����� �� �����, �� ��������, ��� ��� ������ �������, ���������� �������� \rm find\_path, ����� � � ������ ���� ���� ���������, ���� ������ ��������� ���� �����.

������ �� ������������ �������� ����������� ������ m ��������: O((n+m) \log n), ��� (��� m \ge n) �������� ��������������� ����� ������ �� ���� ������ � �������.

��������� ����������� �� �����

���������� ����� ������ ���������, ������� ���� �� ���� �������� �������� ����� ������ ���������, � � ��������� � ���������� ������ ����� � ����� �������� ���������� ����������� ������������ ������� ������ �� ���� ������ � �������.

��� ��������� ����������� � ��������� ��������� ������ {\rm union\_sets}: ���� � ������� ���������� ��, ����� ������ ����� ������������ � ������, ������������ ��������, �� ������ �� ����� ��� ������ �� ������ ������.

���� ��� �������� �������� ���������: � ����� �������� ������ ������ ���������� ���������� ������ � ���, � ������ — ������� ������ (������, ������� ������� �� ������� ������, ��������� ��� ���������� ���������� ��������� ������ ����� �������� ������� ������ ����� �����������).

� ����� ��������� ���� ��������� ���� � �� ��: ��� ���������� \rm union\_sets ����� ������������ ������ � ������� ������ � ������ � ������� ������.

������� ���������� �������� ��������� �� ������ �������� ��������:

void make_set (int v) {
	parent[v] = v;
	size[v] = 1;
}
 
void union_sets (int a, int b) {
	a = find_set (a);
	b = find_set (b);
	if (a != b) {
		if (size[a] < size[b])
			swap (a, b);
		parent[b] = a;
		size[a] += size[b];
	}
}

������� ���������� �������� ��������� �� ������ ������� ��������:

void make_set (int v) {
	parent[v] = v;
	rank[v] = 0;
}
 
void union_sets (int a, int b) {
	a = find_set (a);
	b = find_set (b);
	if (a != b) {
		if (rank[a] < rank[b])
			swap (a, b);
		parent[b] = a;
		if (rank[a] == rank[b])
			++rank[a];
	}
}

��� �������� �������� ��������� �������� �������������� � ����� ������ �����������, ������� �� �������� ����� ��������� ����� �� ���.

������ ����������� ��� ���������� �������� ���������

�������, ��� ����������� ������ ������� ���������������� �������� ��� ������������� ������ �������� ���������, ��� ��������� ������ �����, ����� ��������������� �� ���� ������ � �������: O (\log n).

����� �� �������, ��� ��� ����� �� ���� ��������� �������� ��������� ������� ������� ������ ����� ��������� O (\log n), ��� ������������� ����� �������� ��������������� ����������� ��� ������� \rm find\_set, �, �������������, ������� \rm union\_sets.

���������� �������� ��������� �� ������� ������. �������, ��� ���� ���� ������ ����� k, �� ��� ������ �������� ��� ������� 2^k ������ (������ ����� ������������� ���������, ��� ����, �, ������, � ������� ������, ���� �������� O(\log n)). ���������� ����� �� ��������: ��� k=0 ��� ��������. ��� ������ ����� ������� ����� ������ �����������. ���� ������ ������������� � k-1 �� k, ����� � ���� �������������� ������ ����� k-1; �������� � ���� ���� �������� ������� k-1 ������������� ��������, ��������, ��� ����� ������ ����� k ������������� ����� ����� ��� ������� 2^k ������, ��� � ����������� ��������.

���������� ������ �������� ��������� �� �������� ��������. �������, ��� ���� ������ ������ ����� k, �� ��� ������ �� ����� \lfloor \log k \rfloor. ���������� ����� �� ��������: ��� k=1 ����������� �����. ��� ������ ����� ������� ����� ������ �����������, ������� ������ ����� ������ �� ��������. ����� ������ ������������ ��� ������ �������� k_1 � k_2; ����� �� ������������� �������� �� ������ ������ ���� �����, ��������������, \lfloor \log k_1 \rfloor � \lfloor \log k_2 \rfloor. �� ����� ��������, �������, ��� ������ ������ — ������� (k_1 \ge k_2), ������� ����� ����������� ������� ������������� ������ �� k_1+k_2 ������ ������ �����:

 h = \max ( \lfloor \log k_1 \rfloor, 1 + \lfloor [...]

����� ��������� ��������������, ���� ��������, ���:

 h ~ \stackrel{?}{\le} ~ \lfloor \log (k_1+k_2) \r[...]
 2^h = \max ( 2 ^ {\lfloor \log k_1 \rfloor}, 2 ^ [...]

��� ���� ����� ��������� �����������, ��������� k_1 \le k_1+k_2 � 2 k_2 \le k_1+k_2.

����������� ��������: ������ ���� ���� �������� ���������

��� ��� ����������� ����, ���������� ���������� ���� �������� ��� �������� ��������� ���������, � ����� �������� ����������� ������������ ������� ������.

�� �� ����� ��������� ����� �������������� �����������, ��������� ��� ������ ������� (��., ��������, ������, ���������, ������, ����� "���������. ���������� � ������"). ������� ��� �������������� ���� ��������� �������� (1975 �.).

������������� ��������� �����: ��� ���������� ���������� �������� ������ ���� � ����������� �� ����� ����� ������ �� ���� ������ ���������� O (\alpha(n)) � �������, ��� \alpha(n) — �������� ������� ���������, ������� ����� ����� ��������, ��������� ��������, ��� ��� ���� �������� ����������� n ��� �� ����������� 4 (�������� ��� n \le 10^{600}).

������ ������� ��� ����������� ������ ������� ���������������� �������� ������� �������� "����� ����������� ����� ������".

������� ����� �������� ���������� ������� ���������������� ��������, ����������� ��� ��������� ��������� (������������ �������� ��������� ������������ ������ ��������):

void make_set (int v) {
	parent[v] = v;
	rank[v] = 0;
}
 
int find_set (int v) {
	if (v == parent[v])
		return v;
	return parent[v] = find_set (parent[v]);
}
 
void union_sets (int a, int b) {
	a = find_set (a);
	b = find_set (b);
	if (a != b) {
		if (rank[a] < rank[b])
			swap (a, b);
		parent[b] = a;
		if (rank[a] == rank[b])
			++rank[a];
	}
}

���������� � ������� � ��������� ���������

� ���� ������� �� ���������� ��������� ���������� ��������� ������ "������� ���������������� ��������", ��� �����������, ��� � ������������ ��������� ��������� ��������� ������.

��������� ��������� ��������� �����

��� ���� �� ��������� ���������� ��������� ������ "������� ���������������� ��������", �������, �� ���� ���������, � ������������� �������� ���� ���������.

��������� ������ ����� �������������� ����� �������: ���������� ��� ������ ����, ���������� � ���� ���� ����� ����������� ������� � ����������������� ����, � ����� ��������� ������� (a,b) — "� ���������� �� ����������� ��������� ����� ������� a � b?".

��������������� �������� ����� ��������� ���� ��������� ������, �� �������� �������, ������� ������������ ���� ������ �� ���������� �������/����� ��� ������ �� �������� ���� ������ — �� ����� ����������� ����� � �������.

��������, ��� ����������� � �������� ����� �� ������ �������� ��� ������������� ��������� �������� ���������� ������������ ��������� ������, �� ����� �� �������� ���������� ������ ����� ���������, ���������� ����������� �� �������� �����.

������ �� �������� ����������� ��������������� ������ ���� ������: ���������� ���� ���� � ������-�� ��������� � ������, � ��������� ������� �� �������� ����. ���� ������ ���� � �������, �.�. �� ������� ����� ������ ��� �������, �� ������ ��� ������ ����� ��������� �������: ���������� ������ ����� ������: ����� �������, ��� � ��� ���� ������ ����, � ������� ����� ����������� ���� (������� ������� ����� ���������� �������, ����� ��������������, � �.�.). ��� ����� � ���������� �������������� ���� ������ �� ������ � ������� ������, ������� ������� ����������� ����.

����� ��������� ��������� �� �����������

���� �� ������� �� ����������� ���������� DSU ����������� � ������� ��������� ������: ������� ����������� n \times m ��������. ���������� �� ����������� �����, �� ����� �� ��� �������� ��������� ������ ��������. ��������� ���������� ������ ������ "�����" ���������� ��������� �� �������� �����������.

��� ������� �� ������ ���������� ��� ����� ������ �����������, ��� ������ ������ ���������� � ������ �������, � ���� ����� ���� ����� — �� �������� {\rm union\_sets}() �� ���� ���� ������. ����� �������, � ��� ����� DSU � nm ���������, ���������������� �������� �����������. ������������ � ����� ������� DSU — � ���� ������� ���������� ���������.

������ ������ ����� ������ ����� � �������������� ������ � ������� (��� ������ � ������), ������ � ���������� ����� ������ ���� ����������� ������������: ��� ����� ������������ ������� ��������� (�������� ������ � ������� �������, ���������� ������� � �������� ���������������� ��������, ����������� ��� ��������� ����� ������), �.�. ��������� ������� O(\min (n, m)) ������.

��������� �������������� ���������� ��� ������� ���������

"������� ���������������� ��������" ��������� ����� ������� ����� �������������� ����������, ����������� �� ����������.

������� ������ — ��� ������� ��������: ��� �� �������, ���� ������� ��� �������� �������� ��������� (���������� ��� ������������ ��� �������� ������ ���������).

����� �������, ������ � ������� ������� ��������� ����� ������� ����� �������������� ��������� � ���������� ������ ����������.

���������� DSU ��� ������ "�������" �� �������. ������ � �������� ����������� � ��������

���� �� ���������������� ���������� DSU ����������� � ���, ��� ���� ���� ����� ���������, � �� ������� �������� ������� �� ������ �����, �� �� ����� ������ (�� ����� ����������� �����) �������� �������� �����, � ������� �� ������, ���� ����� ��������� ����� ���� �� �������� ��������� �����.

��������� �������� ����� ���������� �������� ������ � �������� �����������: ���� ������� ����� L, ������ ������ �������� (�.�. ������ ������� ����� 1) ����� ������� ����. ��������� ������� ���� (l,r,c) — ����������� ������� [l;r] � ���� c. ��������� ����� �������� ���� ������ ������. ������� ��������� ���������� �������, �.�. ������ — � ��������.

��� ������� �� ����� ������� DSU-���������, ������� ��� ������ ������ ����� ������� ������ �� ��������� ������ ������������� ������. ����� �������, ���������� ������ ������ ��������� �� ���� ����, � ����� �������� ������� ���������� — ������ ����� ������� ���������� ����� ��������� �� ������ ����� ����� ����������.

������, ����� ������ ������, �� ������������� ������� ���������� � �������� �������: �� ���������� � �������. ��� ���������� ������� �� ������ ������ ��� � ������� ������ DSU ������� ����� ����� ������������� ������ ������ �������, ������������� �, � ������������� ��������� �� �� �� ��������� ������ ������ ������.

����� �������, �� ����� ���������� ���������� DSU � ���������� ������ �����, �� ��� �������� ��������� (�.�. ��� �����, ��� ������ ������� ����� �����������). �������������, �������� ����������� �������� O(\log n) �� ������ (�������, � ��������� �� ��������� � ������� ����������� ������ ����������).

����������:

void init() {
	for (int i=0; i<L; ++i)
		make_set (i);
}
 
void process_query (int l, int r, int c) {
	for (int v=l; ; ) {
		v = find_set (v);
		if (v >= r)  break;
		answer[v] = c;
		parent[v] = v+1;
	}
}

�������, ����� ����������� ��� ������� � �������� ����������: ����� ������� ��� ������� ��������� � ��������� ������� {\rm end}[], ��� ��� ��������� ������������� (�.�. ����� ������ �����). ����� ����� ����� ���������� ��� ��������� � ���� �� �� �������� ���������, ���������� ����� ������������� ��������� ����� ������ �������. ��� ����� �� ������� ������� �� O(\alpha(n)).

��������� ���������� �� ������

������ � ���������� ����������� ������� ���������������� �������� ��������� ���������� ������������ ���������� �� ������ (�.�. ����� ���� � ����� � ������ �� ������� ������� �� ����� ������).

���� �� �� ���� ��������� ������ �����, �� ������� ���������� �� �� ��������� — ���������� �� ����� ������ ��������� �� ����� ����������� �������, ������� ������� ������� \rm find\_set.

������ � ���������� ������ ����� ��������� ���� ���� ����� ������� � ���� �����. ����� �������, ������ � ������ �������� ������� ������� �������������� ����������: ����� �������� ����� �� ������� � ������.

��� ���������� ������ ������������, ��� ������ {\rm parent}[] � ������� \rm find\_set ������ ���������� �� ���� �����, � ���� �����: �������-������ � ���������� �� ��:

void make_set (int v) {
	parent[v] = make_pair (v, 0);
	rank[v] = 0;
}
 
pair<int,int> find_set (int v) {
	if (v != parent[v].first) {
		int len = parent[v].second;
		parent[v] = find_set (parent[v].first);
		parent[v].second += len;
	}
	return parent[v];
}
 
void union_sets (int a, int b) {
	a = find_set (a) .first;
	b = find_set (b) .first;
	if (a != b) {
		if (rank[a] < rank[b])
			swap (a, b);
		parent[b] = make_pair (a, 1);
		if (rank[a] == rank[b])
			++rank[a];
	}
}

��������� �������� ����� ���� � ������ � �������� ������������ ����� � ������

�� �������� � ������ ���� �� ������, ��� �� ����� ������������ �������� ����� ���� �� ����. ������ �� ��� ���������� ���� �������� � ��������� �����?

���� � ���, ��� ������ ���������� �������� �������� ���� ��������� � ����� �� ��������� �������: ���������� ��� ������ ����, � ���� ����� ����������� ����, � ����� ��������� ������� ���� "�������� �� ���������� ���������, ���������� ������ �������, ����������?".

��� ������� ���� ������ �� ����� ������� ������� ���������������� �������� ��� �������� ��������� ���������, � ������� � ������ ������� �������� ����� ���� �� � ������. ��� �����, �� ����� ������ ���������, ������� �� ���������� ���������� ����� � ��������� ������������ ����� ��� ���: � ������, ���� ����� ����� ����� � ����� � ��� �� ���������� ���������, � ��� ���� ����� ���������� �������� ����� ���� �� ������, �� ���������� ����� ����� ������� � ����������� ����� �������� ����� � ����������� ������� ���������� � ������������.

������� ���������, � ������� �� ������������ ��� ����, — ��� ��, ��� �� ������ ���������, � ������ ���������, ����������� ����������� ���� �������� � ������� \rm union\_sets.

���� �� ��������� ����� (a,b), ����������� ��� ���������� ��������� � ����, �� ��� ������������� ������ ������ � ������� �� ������ ������� ��� ����� ��������, ����� � ���������� � ������ a � b ���������� �� ������ �������� ����� ����.

������ �������, �� ������� ������ ���������� ��� ��������, ������������ ������ ������ ��������� ��� ������������� ��� � ������ ������� ���������. ��������� ����� x �������� ����� ���� �� ������� a �� ������ � ���������, ����� y — �������� ����� ���� �� ������� b �� ������ � ���������, � ����� t — ������� ��������, ������� �� ������ ��������� ��������������� ������. ���� ��������� � �������� a �������������� � ��������� � �������� b, ��������� ����������, �� ����� ������������� � ������� b � �������� �� ��������� � ��������� ������ y, � � ������� a �������� ������ ������ x \oplus t (�������� \oplus ����� ���������� �������� XOR (�������������� ��������)). ��� ���������, ����� ��� ��� �������� �����������, �.�. �� XOR ��� ����� �������. �.�. �������� ��������� �� t:

 x \oplus t \oplus y = 1,

����� �������, �������:

 t = x \oplus y \oplus 1.

����� �������, ���������� �� ����, ����� ��������� �������������� � ������, ���� ������������ ��������� ������� ��� ������� �������� �����, ����������� �� ������ ������ � �������.

������� ���������� DSU � ���������� ���������. ��� � � ���������� ������, � ����� �������� �� ���������� ���� ��� �������� ������� � ���������� �������� \rm find\_set. ����� ����, ��� ������� ��������� �� ������ � ������� {\rm bipartite}[], �������� �� ��� �� ��� ���������� ��� ���.

void make_set (int v) {
	parent[v] = make_pair (v, 0);
	rank[v] = 0;
	bipartite[v] = true;
}
 
pair<int,int> find_set (int v) {
	if (v != parent[v].first) {
		int parity = parent[v].second;
		parent[v] = find_set (parent[v].first);
		parent[v].second ^= parity;
	}
	return parent[v];
}
 
void add_edge (int a, int b) {
	pair<int,int> pa = find_set (a);
	a = pa.first;
	int x = pa.second;
 
	pair<int,int> pb = find_set (b);
	b = pb.first;
	int y = pb.second;
 
	if (a == b) {
		if (x == y)
			bipartite[a] = false;
	}
	else {
		if (rank[a] < rank[b])
			swap (a, b);
		parent[b] = make_pair (a, x ^ y ^ 1);
		bipartite[a] &= bipartite[b];
		if (rank[a] == rank[b])
			++rank[a];
	}
}
 
bool is_bipartite (int v) {
	return bipartite[ find_set(v) .first ];
}

�������� ���������� RMQ (������� �� �������) �� O(\alpha(n)) � ������� � ��������

��������� ������ �������� ��������� �������: ����� ����������� ��������� ������, ������� ������������ ��� ���� ��������: ���������� ���������� ����� {\rm insert}(i) (i = 1 \ldots n) � ����� � ���������� �������� ������������ ����� {\rm extract\_min}(). ����� �������, ��� ������ ����� ����������� ����� ���� ���.

����� ����, �������, ��� ��� ������������������ �������� �������� ��� �������, �.�. ������ — � ��������.

���� ������� ���������. ������ ����, ����� �� ������� �������� �� ������ ������, �������� ����� i = 1 \ldots n, � ���������, ������� �� ����� ������ ��� ����� ������ ����. ��� ����� ��� ���� ����� ������ ������������ ������, ������ ����� ���������� {\rm insert}(i) ����� ����� — ����� ������, ��� ��� � ���� ��� ������, ������� �� ������� �������� ����� i.

����� �������, ����� ���������� ����, ������� �� ������ � �������� ��������.

����� �������� ������� �� O(\log n) � ������� �� ������, ���� �� ��������� �� �������� ��������� � ����� ������ ������� � ������ �������� ������ �� ��������� ������ ������ {\rm extract\_min}(), � ������������ ������ ���� ��� ����������� ���� ������ ����� �����������.

����� ����� �������� ������� � �� O(\alpha(n)), ���� �� ����� ������������ �������� ��������� � ����� ������� � ������ ��������� ����� �������, ��� ��� ������������� (��, ��� � ���������� �������� ������� ����������� ������������� �� ���� ����, ��� ������ ������ ��� ������ ������, — ������ ���� ����� ������� ����).

�������� ���������� LCA (����������� ������ ������ � ������) �� O(\alpha(n)) � ������� � ��������

�������� ������� ���������� LCA �� O(1) � ������� � ������ ������ ������ � ��������������� ������. ���� �������� ������� ���������� �� ������ ���������� ������ LCA ����� ��������� (�������� �� ��������� � ����������� ���������� �����-�������-�������).

�������� DSU � ���� ������ ������ ��������. ���������� ���� ���� ��� ������� ��������� �������� ������

����� �� �������������� �������� �������� DSU �������� ���������� ������� ��������� � ���� ���� ����������� ������ ��� ���������. ��� ����, � ������� �������� ����� ����������� ������ �� ������������� (������) ��� ���������.

�� ������ ������ �������, ��� ��� ������������� ��������� ������: ��� ����������� ���� �������� �� ������ ����� �������� ���� ������ � ����� �������, � ����� �������� ������ � ���� ��������� ������ �� ���� �������.

������, ��� �����������, ���������� ������� ���������, ����������� ��������� ����, ��������� ����������� ������� ����������� ������: �� O(m + n \log n) ��� ���������� m �������� ��� n ����������.

��� ������� ���������� ���������������, ��� �� ������ ����� ��������� ������� �� ���� �������� � �������. ���������� {\rm union\_sets}() ������ ��������� � ������ ����� ����������� �� ����� ������� ������� ������������ ���������, � ����� ������ {\rm find\_set}() — �� ����� O(1) ��� ����� ������� ��������.

������� ����������� O(m + n \log n) ��� ���������� m ��������. ����������� ������������ ������� x � ���������, ��� �� ���� �������������� �������� ����������� {\rm union\_sets}. ����� �� ������� x �������������� ������ ���, �� ����� ����������, ��� ������ ��� ������ ��������� ����� ��� ������� 2. ����� �� x �������������� ������ ��� — ����� ����������, ��� �� ������ � ��������� ������� �� ����� 4 (�.�. �� ��������� ������� ��������� � �������). � ��� ����� — ��������, ��� �� ������� x ����� �������������� �������� \lceil \log n \rceil �������� �����������. ����� �������, � ����� �� ���� �������� ��� ���������� O (n \log n), ���� �� O(1) �� ������ ������ — ��� � ����������� ��������.

������� ������ ����������:

vector<int> lst[MAXN];
int parent[MAXN];
 
void make_set (int v) {
	lst[v] = vector<int> (1, v);
	parent[v] = v;
}
 
int find_set (int v) {
	return parent[v];
}
 
void union_sets (int a, int b) {
	a = find_set (a);
	b = find_set (b);
	if (a != b) {
		if (lst[a].size() < lst[b].size())
			swap (a, b);
		while (!lst[b].empty()) {
			int v = lst[b].back();
			lst[b].pop_back();
			parent[v] = a;
			lst[a].push_back (v);
		}
	}
}

����� ��� ���� ���������� ��������� �������� ��������� � ������� ����� ������������ � ��� ����� DSU, ��� ������� ������ �����.

��������, ���������� ��������� ������: ���� ������, ������� ����� �������� ��������� �����-���� ����� (���� � �� �� ����� ����� ����������� ��������� ��� � ������ �������). ��������� ��� ������ ������� ������ ������ ���������� ��������� ����� � � ���������.

�������� � ���� ������ ��� �� ����, ����� �������� ����� �������: ������ ����� � ������� �� ������, ������� ����� ���������� ��������� �� {\rm set} ����� — ������ ���� ����� � ��������� ���� �������. �����, ����� �������� ����� ��� ������� ������� (����, �������, ��� �� ����) — ���� ������� ����� � ������� �� ���� ����� ���� �������, � ���������� ��� ���������� {\rm set} � ����, ������ �������� � ����� ������� ��� ������� �������. ��� ������������ ����������� ���������� {\rm set} � ���� ��� ��� �������� ��������� ���� ����: ����� ���������� ��� ���������, ������ �������� �� ������ �������� �������� ��������� � �������. � ����� �� ������� ������� �� O (n \log^2 n), ��������� ���������� ������ �������� � {\rm set} ������������ �� O (\log n).

�������� DSU � ����������� ����� ��������� ��������. ����������������. �������� ������ ������ � ����� �� O(\alpha(n)) � ������� � �������

���� �� ������ ���������� ��������� ������ "������� ���������������� ��������" ����������� � ���, ��� ��� ��������� ������� ������������ ��� ������, ��� � �������� ��������� ��������. ������ ��������� ����� �������������� ��� �������� ����������� �������� � �������� �� �������������� ���� ������ ������ ������, � �������� — ��������, ��� ������ ���� ����� ����� ��������� ���������, ��� ������ ������� ��������� ������.

��� ���������� ��� ��������, ��� ������ �������� ��� DSU ������� ������ ������� {\rm parent}[] �� ������ ������ �������, ��������, ������� {\rm real\_parent}[]. �������, ��� ����������� ������ ������� ����� �� �������� �����������: ��������� � ��� ���������� ������ ��� ����������� ���� ��������, � ���� � ����� ��������.

� ������ �������, ��� ���������� �� �������� ������� ��������� ��������� ��������� ��� ������ ��������� ������, �� ����������� ��������� �� �� ������. ��� ��������, ��� � ��� ��� ������� ������, ����� ��� ������������� ���� �� �������� �� ��������� �������, ����� ����� �� ������ ������������ ��� ������ � �������, ������ ������ ����� ������ �������� �������� �� ������� ����� ������������ �����.

�� ������ ������ �������, ��� �������� ���������������� — ����� �������� � ������ ������� �����������. �������������, ��� ���������������� ������ �� ������� v �� ������ �������� �� ���� ������� �� ����� ������, �������� ����� ��������� {\rm parent}[] � {\rm real\_parent}[].

������ �� ����� ���� �� �� ��� �����: ���������� ���� ��������������� �� �� ���� ��������, ������� ������, ����� �������� ���������� ������ �����������, ������ O (\log n) � �������.

����� �������� (������� �������������� �����������) ��. �������� ������ ������ � ����� �� O(\log n) � ������� � �������.

������������ �������������

��������� ������ "������� ���������������� ��������" ���� �������� ������������ �����.

������ �������� ���� ��������� � ���� ���� �������� ���, �� ���� ���������, ������� ������ �������� � ������� � 1964 �. (Galler, Fisher "An Improved Equivalence Algorithm"), ������ ������ ������ ����������� ��� ������� ������� �����.

��������� ������ ����� � ����������� �� �����, ��-��������, ����������� �������� (McIlroy) � ������ (Morris), �, ���������� �� ���, ������� (Tritter).

��������� ����� ���� �������� ���� ������ O(\log^* n) �� ���� �������� � �������, ������ ���������� � �������� � 1973 �. (Hopcroft, Ullman "Set-merging algomthms") — ����� \log^* n — ������������� �������� (��� �������� �������� �������, �� �� �� �� ��������� ��������, ��� �������� ������� ���������).

������� ������ O (\alpha(n)), ��� \alpha(n) — �������� ������� ��������� — ������� ������ � ����� ������ 1975 �. (Tarjan "Efficiency of a Good But Not Linear Set Union Algorithm"). ����� � 1985 �. �� ������ � �������� ������� ��� ��������� ������ ��� ���������� ��������� �������� �������� � �������� ������ ���� (Tarjan, Leeuwen "Worst-Case Analysis of Set Union Algorithms").

�������, ������� � ���� � 1989 �. ��������, ��� � �������� ������ ���������� ����� �������� ��� ������� ���������������� �������� ������ �������� ��� ������� �� O(\alpha(n)) � ������� (Fredman, Saks "The cell probe complexity of dynamic data structures").

�������, ������� ����� ��������, ��� ���� ��������� ������, ������������ ��� ��������� ������ � ������������, ��� ������� ���������������� �������� � ����������� ������ ���� � ����������� �� ����� �������� �� O(1) � �������: Zhang "The Union-Find Problem Is Linear", Wu, Otoo "A Simpler Proof of the Average Case Complexity of Union-Find with Path Compression".

������ � online judges

������ �����, ������� ����� ������ � ������� ������� ���������������� ��������:

����������