���������: 11 Jun 2008 10:56 �������������: 24 Jan 2013 12:47 ������� ���������������� �������� � ������ ������ ��������������� ��������� ������ "������� ���������������� ��������" (�� ���������� "disjoint-set-union", ��� ������ "DSU"). ��� ��������� ������ ������������� ��������� �����������. ���������� ������� ��������� ���������, ������ �� ������� ��������� � ��������� (���� �����������) ���������. �� ���� �������� ����� ���������� ��� �����-���� ���������, � ����� ����� ���������, � ����� ��������� ������ ��������� ��������� �������. �����, � ������������ ��������, �������� ��� ���� �������� — �������� ������ ��������, ������� ���������� � ��������� ���������. ����� �������, ������� ��������� ������ ��������� ������ ������� ����� �� ��� ��������: — ��������� ����� ������� , ������� ��� � ����� ���������, ��������� �� ������ ����. — ���������� ��� ��������� ��������� (���������, � ������� ��������� ������� , � ���������, � ������� ��������� ������� ). — ����������, � ����� ��������� ��������� ��������� ������� . �� ����� ���� ��� ���� ������������ ���� �� ��������� ��������� (���������� �������������� ��� ������� (� ������������ ���������� "leader")). ���� ������������� ���������� � ������ ��������� ����� ���������� ������ (� ����� �������� � �������� �������, � ������, ����� ������� ).��������, ���� ����� ��� �����-�� ���� ��������� ������ ���� � �� �� ��������, �� ��� ��������, ��� ��� �������� ��������� � ����� � ��� �� ���������, � � ��������� ������ — � ������ ����������.
����������� ���� ��������� ������ ��������� ������ ������ �� ���� �������� ����� �� � ������� (����� �������� �� ����������� ��. ���� ����� �������� ���������). ����� � ����� �� ����������� ������ ������ �������������� ������� ���������� DSU, ����������� �������� ����������� � ������� �� ���� ������ ��� ; � ��� (�.�. ����������� ������ ) — � ����� ������� � ������� �� ������ (��. "�������� DSU � ���� ������ ������ ��������"). ���������� ����������� ��������� ������ ����������� �������, � ����� ���� �� ����� ������� ��� ����������. ��������� ��������� �� ����� ������� � ���� ��������: ���� ������ ������������� ������ ���������. ������ ������ — ��� ������������� (�����) ���������. ��� ���������� ��� ��������, ��� �� ������� ������ , � ������� ��� ������� �������� �� ������ ������ �� ��� ������ � ������. ��� ������ �������� ����� �������, ��� �� ������ — ��� ���� (�.�. ������ ������������� � ���� �����). ������� ���������� �� ��� ����� �������� ������ ���������� ������� ���������������� ��������. ��� ����� �������� �������������, �� ����� �� ������� � � ������� ���� ������, ������� � ����� ����� ����������� ����� ������. ����, ��� ���������� � ���������� ��������� �������� � ��� � ������� ������� . ����� ������� ����� ������� (�������� ), �� ������ ������ ������ � ������ � ������� , �������, ��� � ������ — ��� ��� ����. ����� ���������� ��� ��������� (�������� ), �� ������� ����� ������� ���������, � ������� ��������� , � ���������, � ������� ��������� . ���� ������ �������, �� ������ �� ������ — ��� ������, ��� ��������� � ��� ��� ���� ����������. � ��������� ������ ����� ������ �������, ��� ������ ������� ����� (��� ��������) — ��� ����� ����������� ���� ������ � �������. �������, ���������� �������� ������ ������ ( ) ������: �� ����������� �� ������� �� ������� , ���� �� ����� �� �����, �.�. ���� ������ �� ������ �� ���� � ����. ��� �������� ������� ����������� ���������� (�������� ��� ����� ������ �����, � ����� � ������������ �������������). 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;
}�������, ����� ���������� ������� ���������������� �������� ������ ������������. ����� ��������� ������, ����� ����� ���������� ����������� �������� ��������� ��������, ��� ��������� — ��� ������, ������������ � ������� �������. � ���������� ������ ����� ����� �������� �� ����� ����� �� ����� ������� ������� ������, �.�. �� . ��� ������ ������ �� ��� �����������, ������� �� ���������� �������� (����������� ����� ������). ������� ���������� ��� �����������, ������� �������� (���� ����������� �� �����������) ����������� �������� ������. ��������� ������ ���� ��� ��������� ������������� ��� ��������� ������ . ��� ����������� � ���, ��� ����� ����� ������ �� ����� �������� ������ ���������, �� ��������, ��� � ������� � ���� ���������� �� ���� ������ — ������ ���� ����� . ����� ����� ��� �������, ������������ �� �� ��� ������� . ����� �������, � ������� ������� ����� ��������� ��������: ������ ��� ������ ������ �������, �.�. ��� ������ ������� ��� ����� ��������� �� ���������������� ������, � ������ ������, ������ ������ ������, � �.�. � ������ �������, �������, ��� ������ �������, ����� ��� ��������� ������ ��������� �� ������: ����� ��� ���������� �������� �������� �� ��������� ������� � ���������. ����� �������, � ������� ������� ��������� ������ ��� � ������� �������, ��������, �������� �������. ����� ���������� �������� �������� ��������� �������: int find_set (int v) {
if (v == parent[v])
return v;
return parent[v] = find_set (parent[v]);
}����� ������� ���������� ������ ��, ��� ������������: ������� ���� ����������� ������� ��������� ������ ���������, � �����, � �������� ��������� �����, ���� ����� ������������� ������� ��� ���� ���������� ���������. ����������� ��� �������� ����� � ������������, �� ����� ������� ������������ ��� ������� �� ������: ������ ����� �������� ������, ������ — ��������� ��� ���� �������� ����. �������, �� �������� ������������� ���������� �� ��� ������������� ��������. ������ ����������� ��� ���������� ��������� ������ ���� �������, ��� ���������� ����� ��������� ������ ���� ��������� ������� ��������������� �����������: �� ���� ������ � �������. �������, ���, ��������� �������� ������������ �� ���� ��� ������ �������� � ��� ��������, �� �� ����� ��������������� � �������������� ������ �� ������ ������� ������ �������� . ������ ����� ������� ����� �������� ���� ������� (������� � ����). ���� ������, ��������, ����� ������ ������������� � �������� ������ ���������. ������ �������� ����� �������� ����� ������ ����� �����: (��������, � �������-������ ��� ������ ������, ��� � �������-�������). ����� ��������, ��� ������ ������-���� �������������� ����� ����� ������ ������������� � �������� ������ ���������. ����� ����, �������� ���� �� ������: ����� ��������, ��� ����� ����� ����� , ���� ��� ������ ����������� ������� . ����� �������, ����� ����� — ��� ����� �� �� . ����������� ������ ������������ ������� � ����� �������, ��� �������� ����� � � ������: ������� ��� ����������� (���� ������� �������� �������), ����� ���������� ����� �� � �����-�� ������� (����� ��������� � �������� �������������� � ������� ���������), � ����� ����� �������� ��� ������ ����� � �������� ������� . �������, ��� ��� ���������� ����������� ������ ���������� ������ (��� ������ �����): ��� ��������� ������ ������� ������� �� ���� ������. ���������� ������ ���������� ������ �������� : �� �������� � ������ ����� ���������� ����, ������ ��� ���� ����� ���� � ������������� �� � ������. ���������� ���� ���� � �������� �� ������������ ��������� ����� ������� ������ (�.�. �� ����� ��� �� ������ ����� �� ������ ). ��� ����� �� ��������� ���� �� ������� �������. ���������� ������ ��� ��������� ���� ����� ����. ��� ������� ������ �����, ���� ��� ����� ����� , ����������, ��� � ���� ���� ���� ��� ���� ����� ������ (����� �� ���� �� ������� ��������� ������� �����, ��� ������������� ������������� ������ ). ����� �������, ����� ������ ���� ��� ����� ��������� �� ����� ������ ��� ������� . ��������, ��� ����������� ��� ����� �� �����, �� ��������, ��� ��� ������ �������, ���������� �������� , ����� � � ������ ���� ���� ���������, ���� ������ ��������� ���� �����. ������ �� ������������ �������� ����������� ������ ��������: , ��� (��� ) �������� ��������������� ����� ������ �� ���� ������ � �������. ��������� ����������� �� ����� ���������� ����� ������ ���������, ������� ���� �� ���� �������� �������� ����� ������ ���������, � � ��������� � ���������� ������ ����� � ����� �������� ���������� ����������� ������������ ������� ������ �� ���� ������ � �������. ��� ��������� ����������� � ��������� ��������� ������ : ���� � ������� ���������� ��, ����� ������ ����� ������������ � ������, ������������ ��������, �� ������ �� ����� ��� ������ �� ������ ������. ���� ��� �������� �������� ���������: � ����� �������� ������ ������ ���������� ���������� ������ � ���, � ������ — ������� ������ (������, ������� ������� �� ������� ������, ��������� ��� ���������� ���������� ��������� ������ ����� �������� ������� ������ ����� �����������). � ����� ��������� ���� ��������� ���� � �� ��: ��� ���������� ����� ������������ ������ � ������� ������ � ������ � ������� ������. ������� ���������� �������� ��������� �� ������ �������� ��������: 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];
}
}��� �������� �������� ��������� �������� �������������� � ����� ������ �����������, ������� �� �������� ����� ��������� ����� �� ���. ������ ����������� ��� ���������� �������� ��������� �������, ��� ����������� ������ ������� ���������������� �������� ��� ������������� ������ �������� ���������, ��� ��������� ������ �����, ����� ��������������� �� ���� ������ � �������: . ����� �� �������, ��� ��� ����� �� ���� ��������� �������� ��������� ������� ������� ������ ����� ��������� , ��� ������������� ����� �������� ��������������� ����������� ��� ������� , �, �������������, ������� . ���������� �������� ��������� �� ������� ������. �������, ��� ���� ���� ������ ����� , �� ��� ������ �������� ��� ������� ������ (������ ����� ������������� ���������, ��� ����, �, ������, � ������� ������, ���� �������� ). ���������� ����� �� ��������: ��� ��� ��������. ��� ������ ����� ������� ����� ������ �����������. ���� ������ ������������� � �� , ����� � ���� �������������� ������ ����� ; �������� � ���� ���� �������� ������� ������������� ��������, ��������, ��� ����� ������ ����� ������������� ����� ����� ��� ������� ������, ��� � ����������� ��������. ���������� ������ �������� ��������� �� �������� ��������. �������, ��� ���� ������ ������ ����� , �� ��� ������ �� ����� . ���������� ����� �� ��������: ��� ����������� �����. ��� ������ ����� ������� ����� ������ �����������, ������� ������ ����� ������ �� ��������. ����� ������ ������������ ��� ������ �������� � ; ����� �� ������������� �������� �� ������ ������ ���� �����, ��������������, � . �� ����� ��������, �������, ��� ������ ������ — ������� ( ), ������� ����� ����������� ������� ������������� ������ �� ������ ������ �����: ![h = \max ( \lfloor \log k_1 \rfloor, 1 + \lfloor [...]](/asset?u=http%3A%2F%2Fe-maxx.ru%2Ftex2png%2Fcache%2F313f05c20a10998025aecd44f88de465.png)
����� ��������� ��������������, ���� ��������, ���: ![h ~ \stackrel{?}{\le} ~ \lfloor \log (k_1+k_2) \r[...]](/asset?u=http%3A%2F%2Fe-maxx.ru%2Ftex2png%2Fcache%2Fc1947a313ad0a57f821bcbbda7c376fe.png)
![2^h = \max ( 2 ^ {\lfloor \log k_1 \rfloor}, 2 ^ [...]](/asset?u=http%3A%2F%2Fe-maxx.ru%2Ftex2png%2Fcache%2F0fc0ea2e7d0c6a74aaa63dee25719e2d.png)
��� ���� ����� ��������� �����������, ��������� � . ����������� ��������: ������ ���� ���� �������� ��������� ��� ��� ����������� ����, ���������� ���������� ���� �������� ��� �������� ��������� ���������, � ����� �������� ����������� ������������ ������� ������. �� �� ����� ��������� ����� �������������� �����������, ��������� ��� ������ ������� (��., ��������, ������, ���������, ������, ����� "���������. ���������� � ������"). ������� ��� �������������� ���� ��������� �������� (1975 �.). ������������� ��������� �����: ��� ���������� ���������� �������� ������ ���� � ����������� �� ����� ����� ������ �� ���� ������ ���������� � �������, ��� — �������� ������� ���������, ������� ����� ����� ��������, ��������� ��������, ��� ��� ���� �������� ����������� ��� �� ����������� 4 (�������� ��� ). ������ ������� ��� ����������� ������ ������� ���������������� �������� ������� �������� "����� ����������� ����� ������". ������� ����� �������� ���������� ������� ���������������� ��������, ����������� ��� ��������� ��������� (������������ �������� ��������� ������������ ������ ��������): 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];
}
} ���������� � ������� � ��������� ��������� � ���� ������� �� ���������� ��������� ���������� ��������� ������ "������� ���������������� ��������", ��� �����������, ��� � ������������ ��������� ��������� ��������� ������. ��������� ��������� ��������� ����� ��� ���� �� ��������� ���������� ��������� ������ "������� ���������������� ��������", �������, �� ���� ���������, � ������������� �������� ���� ���������. ��������� ������ ����� �������������� ����� �������: ���������� ��� ������ ����, ���������� � ���� ���� ����� ����������� ������� � ����������������� ����, � ����� ��������� ������� — "� ���������� �� ����������� ��������� ����� ������� � ?". ��������������� �������� ����� ��������� ���� ��������� ������, �� �������� �������, ������� ������������ ���� ������ �� ���������� �������/����� ��� ������ �� �������� ���� ������ — �� ����� ����������� ����� � �������. ��������, ��� ����������� � �������� ����� �� ������ �������� ��� ������������� ��������� �������� ���������� ������������ ��������� ������, �� ����� �� �������� ���������� ������ ����� ���������, ���������� ����������� �� �������� �����. ������ �� �������� ����������� ��������������� ������ ���� ������: ���������� ���� ���� � ������-�� ��������� � ������, � ��������� ������� �� �������� ����. ���� ������ ���� � �������, �.�. �� ������� ����� ������ ��� �������, �� ������ ��� ������ ����� ��������� �������: ���������� ������ ����� ������: ����� �������, ��� � ��� ���� ������ ����, � ������� ����� ����������� ���� (������� ������� ����� ���������� �������, ����� ��������������, � �.�.). ��� ����� � ���������� �������������� ���� ������ �� ������ � ������� ������, ������� ������� ����������� ����. ����� ��������� ��������� �� ����������� ���� �� ������� �� ����������� ���������� DSU ����������� � ������� ��������� ������: ������� ����������� ��������. ���������� �� ����������� �����, �� ����� �� ��� �������� ��������� ������ ��������. ��������� ���������� ������ ������ "�����" ���������� ��������� �� �������� �����������. ��� ������� �� ������ ���������� ��� ����� ������ �����������, ��� ������ ������ ���������� � ������ �������, � ���� ����� ���� ����� — �� �������� �� ���� ���� ������. ����� �������, � ��� ����� DSU � ���������, ���������������� �������� �����������. ������������ � ����� ������� DSU — � ���� ������� ���������� ���������. ������ ������ ����� ������ ����� � �������������� ������ � ������� (��� ������ � ������), ������ � ���������� ����� ������ ���� ����������� ������������: ��� ����� ������������ ������� ��������� (�������� ������ � ������� �������, ���������� ������� � �������� ���������������� ��������, ����������� ��� ��������� ����� ������), �.�. ��������� ������� ������. ��������� �������������� ���������� ��� ������� ��������� "������� ���������������� ��������" ��������� ����� ������� ����� �������������� ����������, ����������� �� ����������. ������� ������ — ��� ������� ��������: ��� �� �������, ���� ������� ��� �������� �������� ��������� (���������� ��� ������������ ��� �������� ������ ���������). ����� �������, ������ � ������� ������� ��������� ����� ������� ����� �������������� ��������� � ���������� ������ ����������. ���������� DSU ��� ������ "�������" �� �������. ������ � �������� ����������� � �������� ���� �� ���������������� ���������� DSU ����������� � ���, ��� ���� ���� ����� ���������, � �� ������� �������� ������� �� ������ �����, �� �� ����� ������ (�� ����� ����������� �����) �������� �������� �����, � ������� �� ������, ���� ����� ��������� ����� ���� �� �������� ��������� �����. ��������� �������� ����� ���������� �������� ������ � �������� �����������: ���� ������� ����� , ������ ������ �������� (�.�. ������ ������� ����� ) ����� ������� ����. ��������� ������� ���� — ����������� ������� � ���� . ��������� ����� �������� ���� ������ ������. ������� ��������� ���������� �������, �.�. ������ — � ��������. ��� ������� �� ����� ������� DSU-���������, ������� ��� ������ ������ ����� ������� ������ �� ��������� ������ ������������� ������. ����� �������, ���������� ������ ������ ��������� �� ���� ����, � ����� �������� ������� ���������� — ������ ����� ������� ���������� ����� ��������� �� ������ ����� ����� ����������. ������, ����� ������ ������, �� ������������� ������� ���������� � �������� �������: �� ���������� � �������. ��� ���������� ������� �� ������ ������ ��� � ������� ������ DSU ������� ����� ����� ������������� ������ ������ �������, ������������� �, � ������������� ��������� �� �� �� ��������� ������ ������ ������. ����� �������, �� ����� ���������� ���������� DSU � ���������� ������ �����, �� ��� �������� ��������� (�.�. ��� �����, ��� ������ ������� ����� �����������). �������������, �������� ����������� �������� �� ������ (�������, � ��������� �� ��������� � ������� ����������� ������ ����������). ����������: 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;
}
}�������, ����� ����������� ��� ������� � �������� ����������: ����� ������� ��� ������� ��������� � ��������� ������� , ��� ��� ��������� ������������� (�.�. ����� ������ �����). ����� ����� ����� ���������� ��� ��������� � ���� �� �� �������� ���������, ���������� ����� ������������� ��������� ����� ������ �������. ��� ����� �� ������� ������� �� . ��������� ���������� �� ������ ������ � ���������� ����������� ������� ���������������� �������� ��������� ���������� ������������ ���������� �� ������ (�.�. ����� ���� � ����� � ������ �� ������� ������� �� ����� ������). ���� �� �� ���� ��������� ������ �����, �� ������� ���������� �� �� ��������� — ���������� �� ����� ������ ��������� �� ����� ����������� �������, ������� ������� ������� . ������ � ���������� ������ ����� ��������� ���� ���� ����� ������� � ���� �����. ����� �������, ������ � ������ �������� ������� ������� �������������� ����������: ����� �������� ����� �� ������� � ������. ��� ���������� ������ ������������, ��� ������ � ������� ������ ���������� �� ���� �����, � ���� �����: �������-������ � ���������� �� ��: 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];
}
} ��������� �������� ����� ���� � ������ � �������� ������������ ����� � ������ �� �������� � ������ ���� �� ������, ��� �� ����� ������������ �������� ����� ���� �� ����. ������ �� ��� ���������� ���� �������� � ��������� �����? ���� � ���, ��� ������ ���������� �������� �������� ���� ��������� � ����� �� ��������� �������: ���������� ��� ������ ����, � ���� ����� ����������� ����, � ����� ��������� ������� ���� "�������� �� ���������� ���������, ���������� ������ �������, ����������?". ��� ������� ���� ������ �� ����� ������� ������� ���������������� �������� ��� �������� ��������� ���������, � ������� � ������ ������� �������� ����� ���� �� � ������. ��� �����, �� ����� ������ ���������, ������� �� ���������� ���������� ����� � ��������� ������������ ����� ��� ���: � ������, ���� ����� ����� ����� � ����� � ��� �� ���������� ���������, � ��� ���� ����� ���������� �������� ����� ���� �� ������, �� ���������� ����� ����� ������� � ����������� ����� �������� ����� � ����������� ������� ���������� � ������������. ������� ���������, � ������� �� ������������ ��� ����, — ��� ��, ��� �� ������ ���������, � ������ ���������, ����������� ����������� ���� �������� � ������� . ���� �� ��������� ����� , ����������� ��� ���������� ��������� � ����, �� ��� ������������� ������ ������ � ������� �� ������ ������� ��� ����� ��������, ����� � ���������� � ������ � ���������� �� ������ �������� ����� ����. ������ �������, �� ������� ������ ���������� ��� ��������, ������������ ������ ������ ��������� ��� ������������� ��� � ������ ������� ���������. ��������� ����� �������� ����� ���� �� ������� �� ������ � ���������, ����� — �������� ����� ���� �� ������� �� ������ � ���������, � ����� — ������� ��������, ������� �� ������ ��������� ��������������� ������. ���� ��������� � �������� �������������� � ��������� � �������� , ��������� ����������, �� ����� ������������� � ������� � �������� �� ��������� � ��������� ������ , � � ������� �������� ������ ������ (�������� ����� ���������� �������� XOR (�������������� ��������)). ��� ���������, ����� ��� ��� �������� �����������, �.�. �� XOR ��� ����� �������. �.�. �������� ��������� �� : 
����� �������, �������: 
����� �������, ���������� �� ����, ����� ��������� �������������� � ������, ���� ������������ ��������� ������� ��� ������� �������� �����, ����������� �� ������ ������ � �������. ������� ���������� DSU � ���������� ���������. ��� � � ���������� ������, � ����� �������� �� ���������� ���� ��� �������� ������� � ���������� �������� . ����� ����, ��� ������� ��������� �� ������ � ������� , �������� �� ��� �� ��� ���������� ��� ���. 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 (������� �� �������) �� � ������� � �������� ��������� ������ �������� ��������� �������: ����� ����������� ��������� ������, ������� ������������ ��� ���� ��������: ���������� ���������� ����� ( ) � ����� � ���������� �������� ������������ ����� . ����� �������, ��� ������ ����� ����������� ����� ���� ���. ����� ����, �������, ��� ��� ������������������ �������� �������� ��� �������, �.�. ������ — � ��������. ���� ������� ���������. ������ ����, ����� �� ������� �������� �� ������ ������, �������� ����� , � ���������, ������� �� ����� ������ ��� ����� ������ ����. ��� ����� ��� ���� ����� ������ ������������ ������, ������ ����� ���������� ����� ����� — ����� ������, ��� ��� � ���� ��� ������, ������� �� ������� �������� ����� . ����� �������, ����� ���������� ����, ������� �� ������ � �������� ��������. ����� �������� ������� �� � ������� �� ������, ���� �� ��������� �� �������� ��������� � ����� ������ ������� � ������ �������� ������ �� ��������� ������ ������ , � ������������ ������ ���� ��� ����������� ���� ������ ����� �����������. ����� ����� �������� ������� � �� , ���� �� ����� ������������ �������� ��������� � ����� ������� � ������ ��������� ����� �������, ��� ��� ������������� (��, ��� � ���������� �������� ������� ����������� ������������� �� ���� ����, ��� ������ ������ ��� ������ ������, — ������ ���� ����� ������� ����). �������� ���������� LCA (����������� ������ ������ � ������) �� � ������� � �������� �������� ������� ���������� LCA �� � ������� � ������ ������ ������ � ��������������� ������. ���� �������� ������� ���������� �� ������ ���������� ������ LCA ����� ��������� (�������� �� ��������� � ����������� ���������� �����-�������-�������). �������� DSU � ���� ������ ������ ��������. ���������� ���� ���� ��� ������� ��������� �������� ������ ����� �� �������������� �������� �������� DSU �������� ���������� ������� ��������� � ���� ���� ����������� ������ ��� ���������. ��� ����, � ������� �������� ����� ����������� ������ �� ������������� (������) ��� ���������. �� ������ ������ �������, ��� ��� ������������� ��������� ������: ��� ����������� ���� �������� �� ������ ����� �������� ���� ������ � ����� �������, � ����� �������� ������ � ���� ��������� ������ �� ���� �������. ������, ��� �����������, ���������� ������� ���������, ����������� ��������� ����, ��������� ����������� ������� ����������� ������: �� ��� ���������� �������� ��� ����������. ��� ������� ���������� ���������������, ��� �� ������ ����� ��������� ������� �� ���� �������� � �������. ���������� ������ ��������� � ������ ����� ����������� �� ����� ������� ������� ������������ ���������, � ����� ������ — �� ����� ��� ����� ������� ��������. ������� ����������� ��� ���������� ��������. ����������� ������������ ������� � ���������, ��� �� ���� �������������� �������� ����������� . ����� �� ������� �������������� ������ ���, �� ����� ����������, ��� ������ ��� ������ ��������� ����� ��� ������� . ����� �� �������������� ������ ��� — ����� ����������, ��� �� ������ � ��������� ������� �� ����� (�.�. �� ��������� ������� ��������� � �������). � ��� ����� — ��������, ��� �� ������� ����� �������������� �������� �������� �����������. ����� �������, � ����� �� ���� �������� ��� ���������� , ���� �� �� ������ ������ — ��� � ����������� ��������. ������� ������ ����������: 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, ��� ������� ������ �����. ��������, ���������� ��������� ������: ���� ������, ������� ����� �������� ��������� �����-���� ����� (���� � �� �� ����� ����� ����������� ��������� ��� � ������ �������). ��������� ��� ������ ������� ������ ������ ���������� ��������� ����� � � ���������. �������� � ���� ������ ��� �� ����, ����� �������� ����� �������: ������ ����� � ������� �� ������, ������� ����� ���������� ��������� �� ����� — ������ ���� ����� � ��������� ���� �������. �����, ����� �������� ����� ��� ������� ������� (����, �������, ��� �� ����) — ���� ������� ����� � ������� �� ���� ����� ���� �������, � ���������� ��� ���������� � ����, ������ �������� � ����� ������� ��� ������� �������. ��� ������������ ����������� ���������� � ���� ��� ��� �������� ��������� ���� ����: ����� ���������� ��� ���������, ������ �������� �� ������ �������� �������� ��������� � �������. � ����� �� ������� ������� �� , ��������� ���������� ������ �������� � ������������ �� . �������� DSU � ����������� ����� ��������� ��������. ����������������. �������� ������ ������ � ����� �� � ������� � ������� ���� �� ������ ���������� ��������� ������ "������� ���������������� ��������" ����������� � ���, ��� ��� ��������� ������� ������������ ��� ������, ��� � �������� ��������� ��������. ������ ��������� ����� �������������� ��� �������� ����������� �������� � �������� �� �������������� ���� ������ ������ ������, � �������� — ��������, ��� ������ ���� ����� ����� ��������� ���������, ��� ������ ������� ��������� ������. ��� ���������� ��� ��������, ��� ������ �������� ��� DSU ������� ������ ������� �� ������ ������ �������, ��������, ������� . �������, ��� ����������� ������ ������� ����� �� �������� �����������: ��������� � ��� ���������� ������ ��� ����������� ���� ��������, � ���� � ����� ��������. � ������ �������, ��� ���������� �� �������� ������� ��������� ��������� ��������� ��� ������ ��������� ������, �� ����������� ��������� �� �� ������. ��� ��������, ��� � ��� ��� ������� ������, ����� ��� ������������� ���� �� �������� �� ��������� �������, ����� ����� �� ������ ������������ ��� ������ � �������, ������ ������ ����� ������ �������� �������� �� ������� ����� ������������ �����. �� ������ ������ �������, ��� �������� ���������������� — ����� �������� � ������ ������� �����������. �������������, ��� ���������������� ������ �� ������� �� ������ �������� �� ���� ������� �� ����� ������, �������� ����� ��������� � . ������ �� ����� ���� �� �� ��� �����: ���������� ���� ��������������� �� �� ���� ��������, ������� ������, ����� �������� ���������� ������ �����������, ������ � �������. ����� �������� (������� �������������� �����������) ��. �������� ������ ������ � ����� �� � ������� � �������. ������������ ������������� ��������� ������ "������� ���������������� ��������" ���� �������� ������������ �����. ������ �������� ���� ��������� � ���� ���� �������� ���, �� ���� ���������, ������� ������ �������� � ������� � 1964 �. (Galler, Fisher "An Improved Equivalence Algorithm"), ������ ������ ������ ����������� ��� ������� ������� �����. ��������� ������ ����� � ����������� �� �����, ��-��������, ����������� �������� (McIlroy) � ������ (Morris), �, ���������� �� ���, ������� (Tritter). ��������� ����� ���� �������� ���� ������ �� ���� �������� � �������, ������ ���������� � �������� � 1973 �. (Hopcroft, Ullman "Set-merging algomthms") — ����� — ������������� �������� (��� �������� �������� �������, �� �� �� �� ��������� ��������, ��� �������� ������� ���������). ������� ������ , ��� — �������� ������� ��������� — ������� ������ � ����� ������ 1975 �. (Tarjan "Efficiency of a Good But Not Linear Set Union Algorithm"). ����� � 1985 �. �� ������ � �������� ������� ��� ��������� ������ ��� ���������� ��������� �������� �������� � �������� ������ ���� (Tarjan, Leeuwen "Worst-Case Analysis of Set Union Algorithms"). �������, ������� � ���� � 1989 �. ��������, ��� � �������� ������ ���������� ����� �������� ��� ������� ���������������� �������� ������ �������� ��� ������� �� � ������� (Fredman, Saks "The cell probe complexity of dynamic data structures"). �������, ������� ����� ��������, ��� ���� ��������� ������, ������������ ��� ��������� ������ � ������������, ��� ������� ���������������� �������� � ����������� ������ ���� � ����������� �� ����� �������� �� � �������: 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 ������ �����, ������� ����� ������ � ������� ������� ���������������� ��������: ����������
|