Tập rời rạc Union Python

Question

Mô tả dự án

Nội dung chính Show

Mô tả dự án
điều kiện tiên quyết
Cài đặt
Cách sử dụng
Đóng góp
Giấy phép
Xây dựng cấu trúc dữ liệu hiệu quả
Thực hiện ngây thơ
Tối ưu hóa nén đường dẫn
Liên minh theo quy mô / cấp bậc
Độ phức tạp về thời gian
Liên kết theo chỉ mục / liên kết lật đồng xu
Các ứng dụng và cải tiến khác nhau
Các thành phần được kết nối trong biểu đồ
Tìm kiếm các thành phần được kết nối trong một hình ảnh
Lưu trữ thông tin bổ sung cho mỗi bộ
Nén các bước nhảy dọc theo một đoạn / Vẽ các mảng con nhé
Hỗ trợ khoảng cách lên đến đại diện
Hỗ trợ tính chẵn lẻ của độ dài đường dẫn / Kiểm tra tính hai bên trực tuyến
RMQ ngoại tuyến (phạm vi truy vấn tối thiểu) ở mức trung bình $O(\alpha(n))$ / Thủ thuật của Arpa
LCA ngoại tuyến (tổ tiên chung thấp nhất trong một cây) ở $O(\alpha(n))$ trung bình
Lưu trữ DSU một cách rõ ràng trong danh sách tập hợp/Ứng dụng ý tưởng này khi hợp nhất các cấu trúc dữ liệu khác nhau
Lưu trữ DSU bằng cách duy trì cấu trúc cây rõ ràng / Tìm kiếm cầu trực tuyến trong $O(\alpha(n))$ trung bình
hồi tưởng lịch sử

DisjointSet (a. k. a. triển khai union–tìm cấu trúc dữ liệu hoặc hợp nhất–tìm tập hợp) cho Python

điều kiện tiên quyết

Yêu cầu duy nhất là cài đặt Python 3, bạn có thể xác minh điều này bằng cách chạy

$ python --version
Python 3.7.2

Cài đặt

pip install disjoint-set

Bạn có thể xác minh rằng bạn đang chạy phiên bản gói mới nhất bằng cách chạy

>>> import disjoint_set
>>> disjoint_set.__version__
'0.7.3'

Cách sử dụng

>>> from disjoint_set import DisjointSet
>>> ds = DisjointSet()
>>> ds.find(1)
1
>>> ds.union(1,2)
>>> ds.find(1)
2
>>> ds.find(2)
2
>>> ds.connected(1,2)
True
>>> ds.connected(1,3)
False

>>> "a" in ds
False
>>> ds.find("a")
'a'
>>> "a" in ds
True

>>> list(ds)
[(1, 2), (2, 2), (3, 3), ('a', 'a')]

>>> list(ds.itersets())
[{1, 2}, {3}, {'a'}]

Đóng góp

Vui lòng mở bất kỳ vấn đề nào trên github

tác giả

Giấy phép

Dự án này được cấp phép theo Giấy phép MIT - xem GIẤY PHÉP. tập tin md để biết chi tiết

Bài viết này thảo luận về cấu trúc dữ liệu Disjoint Set Union hoặc DSU. Thường thì nó còn được gọi là Union Find vì hai hoạt động chính của nó

Cấu trúc dữ liệu này cung cấp các khả năng sau. Chúng tôi được cung cấp một số phần tử, mỗi phần tử là một tập hợp riêng biệt. Một DSU sẽ có một phép toán để kết hợp hai tập hợp bất kỳ và nó sẽ có thể cho biết phần tử cụ thể nằm trong tập hợp nào. Phiên bản cổ điển cũng giới thiệu thao tác thứ ba, nó có thể tạo một tập hợp từ một phần tử mới

Do đó, giao diện cơ bản của cấu trúc dữ liệu này chỉ bao gồm ba thao tác

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

2 - tạo một tập hợp mới bao gồm phần tử mới

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

3

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

4 - hợp nhất hai tập hợp đã chỉ định (tập hợp chứa phần tử

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

5 và tập hợp chứa phần tử

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

6)

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

7 - trả về đại diện (còn gọi là người lãnh đạo) của tập hợp có chứa phần tử

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

3. Đại diện này là một phần tử của tập hợp tương ứng của nó. Nó được chọn trong mỗi tập hợp bởi chính cấu trúc dữ liệu (và có thể thay đổi theo thời gian, cụ thể là sau cuộc gọi

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

9). Đại diện này có thể được sử dụng để kiểm tra xem hai phần tử có thuộc cùng một tập hợp hay không.

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

5 và

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

6 hoàn toàn thuộc cùng một tập hợp, nếu

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];
    }
}

2. Mặt khác, chúng nằm trong các bộ khác nhau

Như được mô tả chi tiết hơn ở phần sau, cấu trúc dữ liệu cho phép bạn thực hiện từng thao tác này trong gần như $O(1)$ thời gian .

Cũng tại một trong các tiểu mục, một cấu trúc thay thế của DSU được giải thích, cấu trúc này đạt được độ phức tạp trung bình chậm hơn là $O(\log n)$, but can be more powerful than the regular DSU structure.

Xây dựng cấu trúc dữ liệu hiệu quả

Chúng tôi sẽ lưu trữ các bộ ở dạng cây. mỗi cây sẽ tương ứng với một bộ. Và gốc của cây sẽ là đại diện/lãnh đạo của tập hợp

Trong hình ảnh sau đây, bạn có thể thấy đại diện của những cây như vậy

Ban đầu, mọi phần tử bắt đầu dưới dạng một tập hợp duy nhất, do đó mỗi đỉnh là cây riêng của nó. Khi đó ta ghép tập hợp chứa phần tử 1 với tập hợp chứa phần tử 2. Khi đó ta ghép tập hợp chứa phần tử thứ 3 với tập hợp chứa phần tử thứ 4. Và ở bước cuối cùng, ta kết hợp tập hợp chứa phần tử 1 và tập hợp chứa phần tử 3

Để triển khai, điều này có nghĩa là chúng ta sẽ phải duy trì một mảng

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];
    }
}

3 lưu trữ tham chiếu đến tổ tiên trực tiếp của nó trong cây

Thực hiện ngây thơ

Chúng ta đã có thể viết triển khai đầu tiên của cấu trúc dữ liệu Disjoint Set Union. Lúc đầu, nó sẽ khá kém hiệu quả, nhưng sau này chúng ta có thể cải thiện nó bằng cách sử dụng hai cách tối ưu hóa, do đó sẽ mất thời gian gần như không đổi cho mỗi lệnh gọi hàm

Như chúng ta đã nói, tất cả thông tin về các tập hợp phần tử sẽ được lưu giữ trong một mảng

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];
    }
}

3

Để tạo một tập hợp mới (thao tác

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

2), chúng ta chỉ cần tạo một cây có gốc ở đỉnh

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

3, nghĩa là nó là tổ tiên của chính nó

Để kết hợp hai tập hợp (phép toán

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

4), trước tiên chúng tôi tìm đại diện của tập hợp có vị trí của

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

5 và đại diện của tập hợp có vị trí của

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

6. Nếu các đại diện giống hệt nhau, chúng tôi không phải làm gì, thì các bộ đã được hợp nhất. Mặt khác, chúng ta có thể chỉ cần xác định rằng một trong các đại diện là cha của đại diện kia - do đó kết hợp hai cây

Cuối cùng là việc thực hiện chức năng tìm đại diện (hoạt động

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

7). chúng ta chỉ cần leo lên tổ tiên của đỉnh

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

3 cho đến khi chúng ta chạm tới gốc, tôi. e. một đỉnh sao cho tham chiếu đến tổ tiên dẫn đến chính nó. Hoạt động này dễ dàng thực hiện đệ quy

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;
}

Tuy nhiên, việc triển khai này không hiệu quả. Dễ dàng xây dựng một ví dụ để cây thoái hóa thành chuỗi dài. Trong trường hợp đó, mỗi cuộc gọi

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

7 có thể mất $O(n)$ thời gian.

Điều này khác xa với sự phức tạp mà chúng ta muốn có (thời gian gần như không đổi). Do đó, chúng tôi sẽ xem xét hai tối ưu hóa sẽ cho phép tăng tốc đáng kể công việc

Tối ưu hóa nén đường dẫn

Tối ưu hóa này được thiết kế để tăng tốc

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]++;
    }
}

3

Nếu chúng ta gọi

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

7 cho một số đỉnh

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

3, chúng ta thực sự tìm thấy đại diện

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]++;
    }
}

6 cho tất cả các đỉnh mà chúng ta ghé thăm trên đường đi giữa

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

3 và đại diện thực tế

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]++;
    }
}

6. Bí quyết là làm cho đường đi của tất cả các nút đó ngắn hơn, bằng cách đặt trực tiếp cha của mỗi đỉnh đã truy cập thành

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]++;
    }
}

6

Bạn có thể xem các hoạt động trong hình ảnh sau đây. Ở bên trái có một cây và ở bên phải có cây nén sau khi gọi

void make_set(int v) {
    parent[v] = v;
    index[v] = rand();
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (index[a] < index[b])
            swap(a, b);
        parent[b] = a;
    }
}

0, cây này rút ngắn đường đi cho các nút đã truy cập 7, 5, 3 và 2

Việc triển khai mới của

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]++;
    }
}

3 như sau

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

Việc thực hiện đơn giản làm những gì đã được dự định. đầu tiên tìm đại diện của tập hợp (đỉnh gốc), sau đó trong quá trình tháo gỡ ngăn xếp, các nút đã truy cập được gắn trực tiếp vào đại diện

Việc sửa đổi hoạt động đơn giản này đã đạt được độ phức tạp về thời gian $O(\log n)$ trung bình cho mỗi cuộc gọi (ở đây không có bằng chứng . Có một sửa đổi thứ hai, điều đó sẽ làm cho nó thậm chí còn nhanh hơn.

Liên minh theo quy mô / cấp bậc

Trong phần tối ưu hóa này, chúng tôi sẽ thay đổi hoạt động của

void make_set(int v) {
    parent[v] = v;
    index[v] = rand();
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (index[a] < index[b])
            swap(a, b);
        parent[b] = a;
    }
}

2. Nói một cách chính xác, chúng ta sẽ thay đổi cây nào được gắn với cây kia. Trong quá trình triển khai ngây thơ, cây thứ hai luôn được gắn vào cây thứ nhất. Trong thực tế, điều đó có thể dẫn đến các cây chứa các chuỗi có độ dài $O(n)$ . Với sự tối ưu hóa này, chúng tôi sẽ tránh điều này bằng cách chọn rất cẩn thận cây nào được gắn vào.

Có nhiều phương pháp phỏng đoán có thể được sử dụng. Phổ biến nhất là hai cách tiếp cận sau. Trong cách tiếp cận đầu tiên, chúng tôi sử dụng kích thước của cây làm thứ hạng và trong cách tiếp cận thứ hai, chúng tôi sử dụng độ sâu của cây (chính xác hơn là giới hạn trên của độ sâu của cây, vì độ sâu sẽ nhỏ hơn khi áp dụng nén đường dẫn)

Trong cả hai cách tiếp cận, bản chất của tối ưu hóa là như nhau. chúng tôi gắn cây có thứ hạng thấp hơn với cây có thứ hạng lớn hơn

Đây là việc thực hiện công đoàn theo kích thước

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];
    }
}

Và đây là việc thực hiện liên kết theo thứ hạng dựa trên độ sâu của cây

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]++;
    }
}

Cả hai tối ưu hóa đều tương đương về độ phức tạp về thời gian và không gian. Vì vậy, trong thực tế, bạn có thể sử dụng bất kỳ trong số họ

Độ phức tạp về thời gian

Như đã đề cập trước đó, nếu chúng ta kết hợp cả hai tối ưu hóa - nén đường dẫn với kết hợp theo kích thước/thứ hạng - chúng ta sẽ đạt được các truy vấn thời gian gần như không đổi. Hóa ra, độ phức tạp thời gian phân bổ cuối cùng là $O(\alpha(n))$ , trong đó . Trên thực tế, nó phát triển rất chậm, đến mức không vượt quá is the inverse Ackermann function, which grows very slowly. In fact it grows so slowly, that it doesn't exceed $4$ $n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$$n$ (approximately $n < 10^{600}$).

Độ phức tạp được khấu hao là tổng thời gian cho mỗi thao tác, được đánh giá qua một chuỗi nhiều thao tác. Ý tưởng là đảm bảo tổng thời gian của toàn bộ chuỗi, đồng thời cho phép các hoạt động đơn lẻ chậm hơn nhiều so với thời gian khấu hao. e. g. trong trường hợp của chúng tôi, một cuộc gọi đơn lẻ có thể mất $O(\log n)$ trong trường hợp xấu nhất, nhưng nếu chúng tôi thực hiện $m$ such calls back to back we will end up with an average time of $O(\alpha(n))$.

Chúng tôi cũng sẽ không trình bày bằng chứng về độ phức tạp của thời gian này, vì nó khá dài và phức tạp.

Ngoài ra, điều đáng nói là DSU có liên kết theo kích thước / thứ hạng, nhưng không nén đường dẫn hoạt động trong $O(\log n)$ time per query.

Liên kết theo chỉ mục / liên kết lật đồng xu

Cả hợp theo thứ hạng và hợp theo kích thước đều yêu cầu bạn lưu trữ dữ liệu bổ sung cho từng bộ và duy trì các giá trị này trong mỗi thao tác hợp. Cũng tồn tại một thuật toán ngẫu nhiên, giúp đơn giản hóa hoạt động hợp nhất một chút. liên kết theo chỉ số

Chúng tôi gán cho mỗi bộ một giá trị ngẫu nhiên được gọi là chỉ mục và chúng tôi đính kèm bộ có chỉ số nhỏ hơn với bộ có chỉ số lớn hơn. Có khả năng là một tập hợp lớn hơn sẽ có chỉ số lớn hơn tập hợp nhỏ hơn, do đó hoạt động này có liên quan chặt chẽ với hợp theo kích thước. Trên thực tế, người ta có thể chứng minh rằng phép toán này có cùng độ phức tạp về thời gian với phép hợp theo kích thước. Tuy nhiên, trong thực tế, nó chậm hơn một chút so với liên kết theo kích thước

Bạn có thể tìm thấy bằng chứng về sự phức tạp và thậm chí nhiều kỹ thuật kết hợp hơn tại đây

void make_set(int v) {
    parent[v] = v;
    index[v] = rand();
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (index[a] < index[b])
            swap(a, b);
        parent[b] = a;
    }
}

Có một quan niệm sai lầm phổ biến rằng chỉ cần tung một đồng xu, để quyết định xem chúng ta gắn bộ nào với bộ kia, có cùng độ phức tạp. Tuy nhiên điều đó không đúng. Bài báo được liên kết ở trên phỏng đoán rằng liên kết lật đồng xu kết hợp với nén đường dẫn có độ phức tạp $\Omega\left(n \frac{\log n}{\log \log n}\right)$ . Và trong các điểm chuẩn, nó hoạt động kém hơn nhiều so với liên kết theo kích thước/xếp hạng hoặc liên kết theo chỉ mục. . And in benchmarks it performs a lot worse than union by size/rank or linking by index.

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rand() % 2)
            swap(a, b);
        parent[b] = a;
    }
}

Các ứng dụng và cải tiến khác nhau

Trong phần này, chúng tôi xem xét một số ứng dụng của cấu trúc dữ liệu, cả ứng dụng thông thường và một số cải tiến đối với cấu trúc dữ liệu

Các thành phần được kết nối trong biểu đồ

Đây là một trong những ứng dụng rõ ràng của DSU

Chính thức vấn đề được xác định theo cách sau. Ban đầu chúng ta có một biểu đồ trống. Chúng ta phải cộng các đỉnh và các cạnh vô hướng, đồng thời trả lời các truy vấn dạng $(a, b)$ - "các đỉnh là $a$ and $b$ in the same connected component of the graph?"

Tại đây, chúng tôi có thể áp dụng trực tiếp cấu trúc dữ liệu và nhận giải pháp xử lý việc thêm một đỉnh hoặc một cạnh và một truy vấn trong thời gian trung bình gần như không đổi

Ứng dụng này khá quan trọng, vì gần như vấn đề tương tự xuất hiện trong thuật toán tìm cây bao trùm tối thiểu của Kruskal. Sử dụng DSU, chúng tôi có thể cải thiện độ phức tạp của $O(m \log n + n^2)$ thành $O . .

Tìm kiếm các thành phần được kết nối trong một hình ảnh

Một trong những ứng dụng của DSU là nhiệm vụ sau. có một hình ảnh của $n \times m$ pixel. Ban đầu tất cả đều có màu trắng, nhưng sau đó một vài điểm ảnh màu đen được vẽ lên. Bạn muốn xác định kích thước của từng thành phần được kết nối màu trắng trong hình ảnh cuối cùng.

Đối với giải pháp, chúng tôi chỉ cần lặp qua tất cả các pixel màu trắng trong hình ảnh, đối với mỗi ô, lặp qua bốn ô lân cận của nó và nếu ô lân cận có màu trắng, hãy gọi

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

9. Như vậy chúng ta sẽ có một DSU với $n m$ các nút tương ứng với pixel ảnh. Các cây kết quả trong DSU là các thành phần được kết nối mong muốn.

Vấn đề cũng có thể được giải quyết bằng DFS hoặc BFS, nhưng phương pháp được mô tả ở đây có một lợi thế. nó có thể xử lý từng hàng ma trận (i. e. để xử lý một hàng, chúng tôi chỉ cần hàng trước đó và hàng hiện tại, đồng thời chỉ cần một DSU được tạo cho các phần tử của một hàng) trong $O(\min(n, m))$< . memory.

Lưu trữ thông tin bổ sung cho mỗi bộ

DSU cho phép bạn dễ dàng lưu trữ thông tin bổ sung trong bộ

Một ví dụ đơn giản là kích thước của các bộ. lưu trữ các kích thước đã được mô tả trong phần Liên kết theo kích thước (thông tin được lưu trữ bởi đại diện hiện tại của tập hợp)

Theo cách tương tự - bằng cách lưu trữ nó tại các nút đại diện - bạn cũng có thể lưu trữ bất kỳ thông tin nào khác về các tập hợp

Nén các bước nhảy dọc theo một đoạn / Vẽ các mảng con nhé

Một ứng dụng phổ biến của DSU là như sau. Có một tập hợp các đỉnh và mỗi đỉnh có một cạnh đi tới một đỉnh khác. Với DSU, bạn có thể tìm thấy điểm kết thúc mà chúng ta có được sau khi lần theo tất cả các cạnh từ một điểm bắt đầu nhất định, trong thời gian gần như không đổi

Một ví dụ điển hình của ứng dụng này là bài toán vẽ các mảng con. Ta có một đoạn có độ dài $L$ , ban đầu mỗi phần tử có màu 0. Chúng ta phải sơn lại mảng con $[l, r]$ bằng màu $c$ for each query $(l, r, c)$. At the end we want to find the final color of each cell. We assume that we know all the queries in advance, i.e. the task is offline.

Đối với giải pháp, chúng ta có thể tạo một DSU, cho mỗi ô lưu trữ một liên kết đến ô không được tô màu tiếp theo. Do đó, ban đầu mỗi ô chỉ vào chính nó. Sau khi vẽ một đoạn được yêu cầu sơn lại, tất cả các ô từ đoạn đó sẽ trỏ đến ô sau đoạn đó

Bây giờ để giải quyết vấn đề này, chúng tôi xem xét các truy vấn theo thứ tự ngược lại. từ cuối cùng đến đầu tiên. Bằng cách này, khi chúng tôi thực hiện một truy vấn, chúng tôi chỉ phải tô chính xác các ô không được tô trong mảng con $[l, r]$ . Tất cả các ô khác đã chứa màu cuối cùng của chúng. Để nhanh chóng lặp lại tất cả các ô không được tô màu, chúng tôi sử dụng DSU. Chúng tôi tìm thấy ô không được sơn ngoài cùng bên trái bên trong một phân đoạn, sơn lại nó và với con trỏ, chúng tôi di chuyển đến ô trống tiếp theo ở bên phải.

Ở đây chúng ta có thể sử dụng DSU với nén đường dẫn, nhưng chúng ta không thể sử dụng liên kết theo thứ hạng/kích thước (vì điều quan trọng là ai sẽ trở thành người lãnh đạo sau khi hợp nhất). Do đó, độ phức tạp sẽ là $O(\log n)$ trên mỗi liên kết (cũng khá nhanh).

Thực hiện

for (int i = 0; i <= L; i++) {
    make_set(i);
}

for (int i = m-1; i >= 0; i--) {
    int l = query[i].l;
    int r = query[i].r;
    int c = query[i].c;
    for (int v = find_set(l); v <= r; v = find_set(v)) {
        answer[v] = c;
        parent[v] = v + 1;
    }
}

Có một tối ưu hóa. Chúng ta có thể sử dụng phép hợp theo thứ hạng, nếu chúng ta lưu trữ ô chưa tô tiếp theo trong một mảng bổ sung

void make_set(int v) {
    parent[v] = v;
    index[v] = rand();
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (index[a] < index[b])
            swap(a, b);
        parent[b] = a;
    }
}

4. Sau đó, chúng ta có thể hợp nhất hai tập hợp thành một được xếp hạng theo kinh nghiệm của chúng và chúng ta có được giải pháp trong $O(\alpha(n))$ .

Hỗ trợ khoảng cách lên đến đại diện

Đôi khi trong các ứng dụng cụ thể của DSU, bạn cần duy trì khoảng cách giữa một đỉnh và đại diện của tập hợp của nó (i. e. độ dài đường dẫn trong cây từ nút hiện tại đến gốc của cây)

Nếu chúng tôi không sử dụng nén đường dẫn, khoảng cách chỉ là số lần gọi đệ quy. Nhưng điều này sẽ không hiệu quả

Tuy nhiên, có thể thực hiện nén đường dẫn, nếu chúng ta lưu trữ khoảng cách đến nút gốc dưới dạng thông tin bổ sung cho mỗi nút

Trong quá trình triển khai, thật thuận tiện khi sử dụng một mảng các cặp cho

void make_set(int v) {
    parent[v] = v;
    index[v] = rand();
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (index[a] < index[b])
            swap(a, b);
        parent[b] = a;
    }
}

5 và hàm

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]++;
    }
}

3 hiện trả về hai số. đại diện của tập hợp và khoảng cách đến nó

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]++;
    }
}

Hỗ trợ tính chẵn lẻ của độ dài đường dẫn / Kiểm tra tính hai bên trực tuyến

Theo cách tương tự như tính toán độ dài đường dẫn đến người dẫn đầu, có thể duy trì tính chẵn lẻ của độ dài đường đi trước anh ta. Tại sao ứng dụng này trong một đoạn riêng biệt?

Yêu cầu bất thường về lưu trữ tính chẵn lẻ của đường dẫn xuất hiện trong tác vụ sau. ban đầu, chúng tôi được cung cấp một biểu đồ trống, nó có thể được thêm các cạnh và chúng tôi phải trả lời các câu hỏi ở dạng "thành phần được liên thông có chứa đỉnh này không?"

Để giải quyết vấn đề này, chúng tôi tạo một DSU để lưu trữ các thành phần và lưu trữ tính chẵn lẻ của đường dẫn đến đại diện cho mỗi đỉnh. Do đó, chúng tôi có thể nhanh chóng kiểm tra xem việc thêm một cạnh có dẫn đến vi phạm tính hai bên hay không. cụ thể là nếu các đầu của cạnh nằm trong cùng một thành phần được kết nối và có cùng độ dài chẵn lẻ với đường dẫn, thì việc thêm cạnh này sẽ tạo ra một chu kỳ có độ dài lẻ và thành phần sẽ mất thuộc tính lưỡng cực

Khó khăn duy nhất mà chúng tôi gặp phải là tính chẵn lẻ theo phương pháp

void make_set(int v) {
    parent[v] = v;
    index[v] = rand();
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (index[a] < index[b])
            swap(a, b);
        parent[b] = a;
    }
}

7

Nếu chúng ta thêm một cạnh $(a, b)$ để kết nối hai thành phần được kết nối thành một, thì khi bạn gắn một cây vào .

Hãy rút ra một công thức, tính toán tính chẵn lẻ được cấp cho phần đầu của tập hợp sẽ được gắn vào một tập hợp khác. Đặt $x$ là tính chẵn lẻ của độ dài đường đi từ đỉnh $a$ up to its leader $A$, and $y$ as the parity of the path length from vertex $b$ up to its leader $B$, and $t$ the desired parity that we have to assign to $B$ after the merge. The path contains the of the three parts: from $B$ đến $b$ , từ $b$ to $a$, which is connected by one edge and therefore has parity $1$, and from $a$ to $A$. Therefore we receive the formula ($\oplus$ biểu thị phép toán XOR).

$$t = x \oplus y \oplus 1$$

Do đó, bất kể chúng ta thực hiện bao nhiêu phép nối, tính chẵn lẻ của các cạnh được chuyển từ đường dẫn này sang đường dẫn khác

Chúng tôi cung cấp việc triển khai DSU hỗ trợ tính chẵn lẻ. Như phần trước chúng ta dùng cặp để lưu tổ tiên và tổ chẵn lẻ. Ngoài ra, đối với mỗi bộ, chúng tôi lưu trữ trong mảng

void make_set(int v) {
    parent[v] = v;
    index[v] = rand();
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (index[a] < index[b])
            swap(a, b);
        parent[b] = a;
    }
}

8 cho dù nó có còn là lưỡng cực hay không

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 ngoại tuyến (phạm vi truy vấn tối thiểu) ở mức trung bình $O(\alpha(n))$ / Thủ thuật của Arpa

Chúng tôi được cung cấp một mảng

void make_set(int v) {
    parent[v] = v;
    index[v] = rand();
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (index[a] < index[b])
            swap(a, b);
        parent[b] = a;
    }
}

9 và chúng tôi phải tính toán một số cực tiểu trong các phân đoạn đã cho của mảng

Ý tưởng để giải quyết vấn đề này với DSU là như sau. Chúng tôi sẽ lặp lại mảng và khi chúng tôi ở phần tử thứ

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rand() % 2)
            swap(a, b);
        parent[b] = a;
    }
}

0, chúng tôi sẽ trả lời tất cả các truy vấn

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rand() % 2)
            swap(a, b);
        parent[b] = a;
    }
}

1 với

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rand() % 2)
            swap(a, b);
        parent[b] = a;
    }
}

2. Để thực hiện điều này một cách hiệu quả, chúng tôi sẽ giữ một DSU sử dụng các phần tử

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rand() % 2)
            swap(a, b);
        parent[b] = a;
    }
}

0 đầu tiên với cấu trúc sau. cha của một phần tử là phần tử nhỏ hơn tiếp theo ở bên phải của nó. Sau đó, sử dụng cấu trúc này, câu trả lời cho một truy vấn sẽ là

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rand() % 2)
            swap(a, b);
        parent[b] = a;
    }
}

4, số nhỏ nhất ở bên phải của

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rand() % 2)
            swap(a, b);
        parent[b] = a;
    }
}

5

Cách tiếp cận này rõ ràng chỉ hoạt động ngoại tuyến, tôi. e. nếu chúng ta biết trước tất cả các truy vấn

Dễ thấy rằng chúng ta có thể áp dụng nén đường dẫn. Và chúng tôi cũng có thể sử dụng Liên minh theo thứ hạng, nếu chúng tôi lưu trữ người lãnh đạo thực tế trong một mảng riêng biệt

struct Query {
    int L, R, idx;
};

vector<int> answer;
vector<vector<Query>> container;

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rand() % 2)
            swap(a, b);
        parent[b] = a;
    }
}

6 chứa tất cả các truy vấn với

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rand() % 2)
            swap(a, b);
        parent[b] = a;
    }
}

2

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

0

Ngày nay thuật toán này được gọi là thủ thuật của Arpa. Nó được đặt theo tên của AmirReza Poorakhavan, người đã độc lập phát hiện và phổ biến kỹ thuật này. Mặc dù thuật toán này đã tồn tại trước khi ông phát hiện ra

LCA ngoại tuyến (tổ tiên chung thấp nhất trong một cây) ở $O(\alpha(n))$ trung bình

Thuật toán tìm LCA được thảo luận trong bài viết Tổ tiên chung thấp nhất - Thuật toán ngoại tuyến của Tarjan. Thuật toán này so sánh thuận lợi với các thuật toán khác để tìm LCA do tính đơn giản của nó (đặc biệt là so với thuật toán tối ưu như thuật toán của Farach-Colton và Bender)

Lưu trữ DSU một cách rõ ràng trong danh sách tập hợp/Ứng dụng ý tưởng này khi hợp nhất các cấu trúc dữ liệu khác nhau

Một trong những cách khác để lưu trữ DSU là lưu trữ từng bộ dưới dạng danh sách các phần tử của nó được lưu trữ rõ ràng. Đồng thời, mỗi phần tử cũng lưu trữ tham chiếu đến đại diện của tập hợp của mình

Thoạt nhìn, đây có vẻ là một cấu trúc dữ liệu không hiệu quả. bằng cách kết hợp hai bộ, chúng tôi sẽ phải thêm một danh sách vào cuối danh sách khác và phải cập nhật vị trí dẫn đầu trong tất cả các thành phần của một trong các danh sách

Tuy nhiên, hóa ra, việc sử dụng heuristic trọng số (tương tự như Union by size) có thể làm giảm đáng kể độ phức tạp tiệm cận. $O(m + n \log n)$ để thực hiện $m$ queries on the $n$ elements.

Theo heuristic theo trọng số, ý của chúng tôi là chúng tôi sẽ luôn thêm tập hợp nhỏ hơn trong hai tập hợp vào tập hợp lớn hơn. Việc thêm tập hợp này vào tập hợp khác rất dễ thực hiện trong

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

9 và sẽ mất thời gian tỷ lệ thuận với kích thước của tập hợp được thêm vào. Và việc tìm kiếm người dẫn đầu trong

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]++;
    }
}

3 sẽ mất $O(1)$ với phương pháp lưu trữ này.

Chúng ta hãy chứng minh độ phức tạp về thời gian $O(m + n \log n)$ để thực hiện $m$ queries. We will fix an arbitrary element $x$ và đếm tần suất nó được chạm vào trong thao tác hợp nhất

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

9. Khi phần tử $x$ được chạm vào lần đầu tiên, kích thước của tập hợp mới sẽ ít nhất là $2 . Khi nó được chạm vào lần thứ hai, tập hợp kết quả sẽ có kích thước ít nhất là . When it gets touched the second time, the resulting set will have size of at least $4$ , bởi vì tập hợp nhỏ hơn được thêm vào tập hợp lớn hơn. Và như thế. Điều này có nghĩa là $x$ chỉ có thể được chuyển vào tối đa $\log n$ merge operations. Thus the sum over all vertices gives $O(n \log n)$ cộng với $O(1)$ . for each request.

Đây là một triển khai

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

1

Ý tưởng thêm phần nhỏ hơn vào phần lớn hơn cũng có thể được sử dụng trong nhiều giải pháp không liên quan gì đến DSU

Ví dụ xét bài toán sau. chúng ta được cho một cái cây, mỗi lá được gán một số (cùng một số có thể xuất hiện nhiều lần trên các lá khác nhau). Chúng tôi muốn tính số lượng các số khác nhau trong cây con cho mọi nút của cây

Áp dụng ý tưởng tương tự cho nhiệm vụ này thì có thể đạt được giải pháp này. chúng ta có thể triển khai DFS, nó sẽ trả về một con trỏ tới một tập hợp các số nguyên - danh sách các số trong cây con đó. Sau đó, để lấy câu trả lời cho nút hiện tại (tất nhiên trừ khi đó là lá), chúng tôi gọi DFS cho tất cả các nút con của nút đó và hợp nhất tất cả các bộ nhận được lại với nhau. Kích thước của tập hợp kết quả sẽ là câu trả lời cho nút hiện tại. Để kết hợp hiệu quả nhiều bộ, chúng tôi chỉ cần áp dụng công thức được mô tả ở trên. chúng tôi hợp nhất các bộ bằng cách thêm các bộ nhỏ hơn vào bộ lớn hơn. Cuối cùng, chúng tôi nhận được giải pháp $O(n \log^2 n)$ , bởi vì một số sẽ chỉ được thêm nhiều nhất vào một tập hợp $O(\log n)$ times.

Lưu trữ DSU bằng cách duy trì cấu trúc cây rõ ràng / Tìm kiếm cầu trực tuyến trong $O(\alpha(n))$ trung bình

Một trong những ứng dụng mạnh mẽ nhất của DSU là nó cho phép bạn lưu trữ cả dưới dạng cây nén và không nén. Dạng nén có thể được sử dụng để hợp nhất các cây và để xác minh xem hai đỉnh có thuộc cùng một cây hay không và dạng không nén có thể được sử dụng - ví dụ - để tìm kiếm các đường dẫn giữa hai đỉnh đã cho hoặc các đường duyệt khác của cấu trúc cây

Trong quá trình triển khai, điều này có nghĩa là ngoài mảng tổ tiên đã nén

void make_set(int v) {
    parent[v] = v;
    index[v] = rand();
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (index[a] < index[b])
            swap(a, b);
        parent[b] = a;
    }
}

5, chúng ta sẽ cần giữ lại mảng tổ tiên không nén

for (int i = 0; i <= L; i++) {
    make_set(i);
}

for (int i = m-1; i >= 0; i--) {
    int l = query[i].l;
    int r = query[i].r;
    int c = query[i].c;
    for (int v = find_set(l); v <= r; v = find_set(v)) {
        answer[v] = c;
        parent[v] = v + 1;
    }
}

2. Việc duy trì mảng bổ sung này sẽ không làm phức tạp thêm. những thay đổi trong nó chỉ xảy ra khi chúng ta hợp nhất hai cây và chỉ trong một phần tử

Mặt khác khi áp dụng vào thực tế ta thường cần nối các cây bằng một cạnh xác định khác với nối hai nút gốc. Điều này có nghĩa là chúng ta không có lựa chọn nào khác ngoài việc root lại một trong các cây (biến các đầu của cạnh thành gốc mới của cây)

Thoạt nhìn, có vẻ như việc root lại này rất tốn kém và sẽ làm phức tạp thời gian hơn rất nhiều. Thật vậy, để tạo gốc cho một cây ở đỉnh $v$ chúng ta phải đi từ đỉnh đến gốc cũ và đổi hướng trong

void make_set(int v) {
    parent[v] = v;
    index[v] = rand();
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (index[a] < index[b])
            swap(a, b);
        parent[b] = a;
    }
}

5 và

for (int i = 0; i <= L; i++) {
    make_set(i);
}

for (int i = m-1; i >= 0; i--) {
    int l = query[i].l;
    int r = query[i].r;
    int c = query[i].c;
    for (int v = find_set(l); v <= r; v = find_set(v)) {
        answer[v] = c;
        parent[v] = v + 1;
    }
}

2 cho tất cả các nút trên .

Tuy nhiên, trên thực tế thì điều đó không tệ lắm, chúng ta chỉ cần root lại cây nhỏ hơn trong số hai cây tương tự như ý tưởng trong các phần trước và nhận được $O( . on average.

Thông tin chi tiết hơn (bao gồm cả bằng chứng về độ phức tạp của thời gian) có thể được tìm thấy trong bài viết Tìm cầu trực tuyến

hồi tưởng lịch sử

Cấu trúc dữ liệu DSU đã được biết đến từ lâu

Cách lưu trữ cấu trúc này dưới dạng một rừng cây rõ ràng đã được Galler và Fisher mô tả lần đầu tiên vào năm 1964 (Galler, Fisher, "Một thuật toán tương đương được cải tiến), tuy nhiên, phân tích đầy đủ về độ phức tạp của thời gian đã được tiến hành muộn hơn nhiều

Nén đường dẫn tối ưu hóa và Liên kết theo thứ hạng đã được phát triển bởi McIlroy và Morris, và độc lập với họ cũng bởi Tritter

programming python