29.1 union-find

โจทย์จำนวนมากในค่าย 2 และ TOI พูดถึง กลุ่ม ที่ค่อยๆ รวมกันใหญ่ขึ้น เช่น ใครเป็นเพื่อนของเพื่อนกับใคร เมืองไหนมีถนนไปถึงกันแล้ว บทที่ 27 หาส่วนเชื่อมต่อด้วย DFS หรือ BFS ได้เมื่อรู้เส้นเชื่อมครบทุกเส้นแล้ว แต่ถ้าเส้นเชื่อมทยอยเพิ่มเข้ามา และมีคำถามแทรกอยู่ระหว่างนั้น การเดินกราฟใหม่ทุกครั้งที่ถามช้าเกินไป หน้านี้สร้างโครงสร้างข้อมูลชื่อ union-find หรือ disjoint set union (DSU) ที่ทำได้สองอย่าง คือรวมสองกลุ่มเข้าด้วยกัน กับบอกว่าสองคนอยู่กลุ่มเดียวกันไหม เริ่มจากแบบตรงไปตรงมา แล้วเพิ่มสองเทคนิคที่ทำให้แต่ละครั้งเร็วจนเกือบเป็นเวลาคงที่ union-find เป็นชิ้นส่วนหลักของ Kruskal ในหน้า 29.3 ด้วย

โจทย์จับกลุ่มทำโครงงาน

ห้องหนึ่งมีนักเรียน N คน หมายเลข 1 ถึง N ตอนเริ่มทุกคนทำงานคนเดียว แล้วมีคำสั่งเข้ามาทีละบรรทัด สองแบบ

join a b กลุ่มของ a กับกลุ่มของ b ตกลงรวมเป็นกลุ่มเดียวกัน ถ้าอยู่กลุ่มเดียวกันอยู่แล้วก็ไม่มีอะไรเปลี่ยน
ask a b ตอนนี้ a กับ b อยู่กลุ่มเดียวกันหรือยัง

ต้องตอบ ask ตามสภาพ ณ ตอนนั้นทันที โจทย์ที่คำถามแทรกอยู่ระหว่างการเปลี่ยนแปลงแบบนี้เรียกว่าโจทย์แบบ ออนไลน์ (online) ถ้าเก็บ join ทุกเส้นเป็นกราฟแล้ว BFS ทุกครั้งที่มี ask หนึ่งคำถามใช้ O(N + M) เมื่อ M คือจำนวนเส้น แสนคำถามก็ช้าไปหลายสิบวินาที หน้า 29.2 จะวัดให้ดู

แต่ละกลุ่มคือต้นไม้

union-find เก็บแต่ละกลุ่มเป็นต้นไม้หนึ่งต้น ทุกคนจำแค่ parent คือคนที่อยู่เหนือตัวเองหนึ่งขั้น แบบอาเรย์ parent ในหน้า 26.1 รากของต้นไม้คือ หัวหน้ากลุ่ม ต่างจากบทที่ 26 ตรงที่รากชี้กลับมาที่ตัวเอง parent[r] = r แทนการเก็บ 0 จะได้เขียนเงื่อนไขหยุดได้สั้น

find หาหัวหน้ากลุ่มของ x คือเดินขึ้นตาม parent จนถึงคนที่ชี้ตัวเอง เหมือนหาความลึกด้วยการเดินขึ้นในหน้า 26.1
union รวมกลุ่มของ a กับ b คือหาหัวหน้าของทั้งสองฝั่ง ถ้าเป็นคนละคน ให้หัวหน้าฝั่งหนึ่งชี้ไปที่หัวหน้าอีกฝั่ง ทั้งต้นไม้จึงไปห้อยอยู่ใต้อีกต้นในก้าวเดียว
a กับ b อยู่กลุ่มเดียวกันก็ต่อเมื่อ find ของทั้งคู่ได้หัวหน้าคนเดียวกัน

รูปร่างของต้นไม้ไม่มีความหมายอะไร ใครอยู่ใต้ใครก็ได้ สิ่งเดียวที่สำคัญคือเดินขึ้นไปแล้วถึงรากเดียวกันไหม ข้อนี้ทำให้เราดัดรูปต้นไม้ได้ตามใจเพื่อให้เร็วขึ้น ซึ่งเป็นเนื้อหาครึ่งหลังของหน้านี้

แบบตรงไปตรงมา

#include <bits/stdc++.h>
using namespace std;

vector<int> parent;

int find_root(int x)
{
    while (parent[x] != x) {
        x = parent[x]; // (1)!
    }
    return x;
}

void unite(int a, int b) // (2)!
{
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a != root_b) {
        parent[root_a] = root_b; // (3)!
    }
}

int main()
{
    int n, q;
    cin >> n >> q;
    parent.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i; // (4)!
    }
    for (int k = 0; k < q; k++) {
        string op;
        int a, b;
        cin >> op >> a >> b;
        if (op == "join") {
            unite(a, b);
        } else {
            cout << "ask " << a << ' ' << b << ": " << (find_root(a) == find_root(b) ? "yes" : "no") << '\n';
        }
    }
    cout << "parent:";
    for (int i = 1; i <= n; i++) {
        cout << ' ' << parent[i];
    }
    cout << '\n';
    return 0;
}

เดินขึ้นทีละขั้นจนถึงคนที่ parent เป็นตัวเอง ซึ่งก็คือหัวหน้ากลุ่ม
ตั้งชื่อว่า unite เพราะ union เป็นคำสงวนของภาษาตั้งแต่หน้า 11.3 ใช้เป็นชื่อฟังก์ชันไม่ได้
ต่อ หัวหน้า เข้ากับ หัวหน้า ไม่ใช่ a เข้ากับ b ตรงๆ ดูเหตุผลในส่วนลองทำให้พัง
ตอนเริ่มทุกคนเป็นหัวหน้าของกลุ่มที่มีคนเดียว

8 9
join 1 2
join 3 4
ask 1 3
join 2 4
ask 1 3
join 5 6
join 6 7
ask 5 8
ask 7 5

ask 1 3: no
ask 1 3: yes
ask 5 8: no
ask 7 5: yes
parent: 2 4 4 4 6 7 7 8

บรรทัดสุดท้ายพิมพ์ parent ของทุกคนให้เห็นต้นไม้ข้างใน join 1 2 ให้ 1 ชี้ 2 join 3 4 ให้ 3 ชี้ 4 คำถามแรกจึงตอบ no เพราะหัวหน้าของ 1 คือ 2 ส่วนหัวหน้าของ 3 คือ 4 พอ join 2 4 หัวหน้า 2 ไปชี้หัวหน้า 4 คำถามเดิมรอบที่สองเดินจาก 1 ไป 2 ไป 4 และจาก 3 ไป 4 ได้หัวหน้าเดียวกัน จึงตอบ yes

ต้นไม้ที่ยาวเป็นเส้น

find เดินกี่ก้าวขึ้นกับความสูงของต้นไม้ แบบตรงไปตรงมาไม่ได้ควบคุมความสูงเลย ลองรวมกลุ่มต่อกันเป็นทอดๆ

6 6
join 1 2
join 2 3
join 3 4
join 4 5
join 5 6
ask 1 6

ask 1 6: yes
parent: 2 3 4 5 6 6

แต่ละ join i i+1 ทำให้หัวหน้าของกลุ่มเดิมทั้งก้อนไปห้อยใต้คนใหม่ ต้นไม้จึงกลายเป็นเส้นตรง 1 ชี้ 2 ชี้ 3 ไปจนถึง 6 ถาม ask 1 6 ต้องเดิน 5 ก้าวกว่าจะเจอหัวหน้า ถ้ามี N คน เส้นนี้ยาว N - 1 ก้าว และถ้าถามเกี่ยวกับคนท้ายเส้น Q ครั้ง ก็ต้องเดินซ้ำทางเดิม Q ครั้ง รวมเป็น O(NQ) ปัญหาเดียวกับการเดินขึ้นบนต้นไม้เส้นตรงในหน้า 26.1 ที่ N กับ Q เป็นแสน คือราว 10¹⁰ ก้าว

path compression

ระหว่างที่ find เดินจาก 1 ขึ้นไปถึง 6 มันผ่าน 2 3 4 5 และรู้แล้วว่าหัวหน้าของทุกคนบนทางนี้คือ 6 ถ้าจดผลนี้ไว้ ให้ทุกคนบนทางชี้ตรงไปที่ 6 เลย ครั้งต่อไปทุกคนก็ถึงหัวหน้าในก้าวเดียว เทคนิคนี้เรียกว่า path compression (บีบทางเดินให้สั้น) ยังเป็นกลุ่มเดิมทุกอย่าง เพราะหัวหน้าไม่เปลี่ยน เปลี่ยนแค่รูปร่างของต้นไม้ ซึ่งเราบอกไว้แล้วว่าไม่มีความหมาย

เขียนด้วย recursion ได้สั้นที่สุด หาหัวหน้าของ parent[x] ก่อน ได้แล้วให้ x ชี้ไปที่หัวหน้านั้นตรงๆ ทุกชั้นของ recursion ทำแบบเดียวกันตอนขากลับ ทุกคนบนทางเดินจึงได้ชี้ตรงไปที่หัวหน้า

#include <bits/stdc++.h>
using namespace std;

vector<int> parent;

int find_root(int x)
{
    if (parent[x] == x) {
        return x;
    }
    parent[x] = find_root(parent[x]); // (1)!
    return parent[x];
}

void unite(int a, int b)
{
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a != root_b) {
        parent[root_a] = root_b;
    }
}

int main()
{
    int n, q;
    cin >> n >> q;
    parent.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    for (int k = 0; k < q; k++) {
        string op;
        int a, b;
        cin >> op >> a >> b;
        if (op == "join") {
            unite(a, b);
        } else {
            cout << "ask " << a << ' ' << b << ": " << (find_root(a) == find_root(b) ? "yes" : "no") << '\n';
        }
    }
    cout << "parent:";
    for (int i = 1; i <= n; i++) {
        cout << ' ' << parent[i];
    }
    cout << '\n';
    return 0;
}

ต่างจากโปรแกรมก่อนแค่ฟังก์ชันนี้ บรรทัดนี้ทั้งหาหัวหน้าและจดผลลง parent[x] ไว้ใช้ครั้งหน้า

6 6
join 1 2
join 2 3
join 3 4
join 4 5
join 5 6
ask 1 6

ask 1 6: yes
parent: 6 6 6 6 6 6

ตอน join ทั้งห้าครั้ง find เรียกกับคนที่เป็นหัวหน้าอยู่แล้วทุกครั้ง ต้นไม้จึงยังเป็นเส้นตรงเหมือนเดิม แต่ ask 1 6 ครั้งเดียวทำให้ parent ของทุกคนกลายเป็น 6

union by size

path compression แก้ทางเดินหลังจากเดินไปแล้วหนึ่งรอบ แต่ find ครั้งแรกบนเส้นที่ยาวยังต้องเดินครบทั้งเส้น และ recursion ก็ลึกเท่าความยาวเส้น ซึ่งมีปัญหาตามส่วนลองทำให้พัง อีกเทคนิคหนึ่งกันไม่ให้ต้นไม้สูงตั้งแต่ตอนรวม ตอน unite เรามีสิทธิ์เลือกว่าจะเอาหัวหน้าฝั่งไหนไปห้อยใต้อีกฝั่ง ลองดูกลุ่มสามคน 1 2 3 กับกลุ่มคนเดียวของ 4

ทุกคนในกลุ่มที่ถูกเอาไปห้อยจะอยู่ลึกลงหนึ่งขั้น ถ้าเอากลุ่มใหญ่ไปห้อย คนสามคนลึกขึ้น ถ้าเอากลุ่มเล็กไปห้อย มีคนเดียวที่ลึกขึ้น จึงจำ group_size ขนาดของกลุ่มไว้ที่หัวหน้า แล้ว เอาหัวหน้าของกลุ่มที่เล็กกว่าไปห้อยใต้หัวหน้าของกลุ่มที่ใหญ่กว่าเสมอ เรียกว่า union by size

ต้นไม้สูงไม่เกิน log₂ N

ดูคนหนึ่งคน สมมติชื่อ x ความลึกของ x เพิ่มขึ้นได้ทางเดียว คือตอนที่หัวหน้าของ x ถูกเอาไปห้อยใต้หัวหน้าอีกกลุ่ม ซึ่งเกิดเฉพาะเมื่อกลุ่มของ x เล็กกว่าหรือเท่ากับอีกกลุ่ม กลุ่มที่รวมเสร็จจึงใหญ่อย่างน้อยสองเท่าของกลุ่มเดิมของ x ทุกครั้งที่ x ลึกขึ้นหนึ่งขั้น กลุ่มของ x ใหญ่ขึ้นอย่างน้อยสองเท่า กลุ่มเริ่มที่ 1 คนและใหญ่ได้ไม่เกิน N คน จึงเป็นสองเท่าได้ไม่เกิน log₂ N ครั้ง x จึงลึกไม่เกิน log₂ N ขั้น N เป็นแสนลึกไม่เกิน 16 ขั้น N เป็นล้านไม่เกิน 19 ขั้น

รวมทั้งสองเทคนิคเข้าด้วยกันเป็นโปรแกรมที่จะใช้ตลอดบทนี้

#include <bits/stdc++.h>
using namespace std;

vector<int> parent, group_size; // (1)!

int find_root(int x)
{
    if (parent[x] == x) {
        return x;
    }
    parent[x] = find_root(parent[x]);
    return parent[x];
}

void unite(int a, int b)
{
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a == root_b) {
        return;
    }
    if (group_size[root_a] < group_size[root_b]) {
        swap(root_a, root_b); // (2)!
    }
    parent[root_b] = root_a;
    group_size[root_a] += group_size[root_b]; // (3)!
}

int main()
{
    int n, q;
    cin >> n >> q;
    parent.resize(n + 1);
    group_size.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    for (int k = 0; k < q; k++) {
        string op;
        int a, b;
        cin >> op >> a >> b;
        if (op == "join") {
            unite(a, b);
        } else {
            cout << "ask " << a << ' ' << b << ": " << (find_root(a) == find_root(b) ? "yes" : "no") << '\n';
        }
    }
    cout << "parent:";
    for (int i = 1; i <= n; i++) {
        cout << ' ' << parent[i];
    }
    cout << '\n';
    return 0;
}

อย่าตั้งชื่อตัวแปรนอก main ว่า size ดูแบบที่ 2 ในส่วนลองทำให้พัง
สลับให้ root_a เป็นกลุ่มที่ใหญ่กว่าหรือเท่ากันเสมอ บรรทัดถัดไปจึงเขียนแบบเดียวได้
ขนาดที่ถูกต้องมีแค่ที่หัวหน้า ขนาดที่ค้างอยู่ใน group_size[root_b] ไม่ได้ใช้อีกแล้ว เพราะ root_b ไม่ใช่หัวหน้าแล้ว

8 9
join 1 2
join 3 4
ask 1 3
join 2 4
ask 1 3
join 5 6
join 6 7
ask 5 8
ask 7 5

ask 1 3: no
ask 1 3: yes
ask 5 8: no
ask 7 5: yes
parent: 1 1 1 3 5 5 5 8

คำตอบเหมือนแบบตรงไปตรงมาทุกบรรทัด แต่ต้นไม้ข้างในต่างกัน join 1 2 สองกลุ่มขนาดเท่ากัน จึงไม่สลับ 2 ไปห้อยใต้ 1 join 2 4 รวมกลุ่ม {1, 2} กับ {3, 4} ซึ่งใหญ่เท่ากัน หัวหน้า 3 จึงไปห้อยใต้หัวหน้า 1 ส่วน join 6 7 กลุ่มของ 6 มีสองคน ใหญ่กว่ากลุ่มของ 7 ที่มีคนเดียว 7 จึงไปห้อยใต้ 5 ไม่ใช่ 5 ไปห้อยใต้ 7 แบบเดิม ถ้าป้อนเส้นตรงหกคนชุดเดิม จะได้ parent: 1 1 1 1 1 1 เพราะทุกครั้งคนใหม่ที่อยู่คนเดียวไปห้อยใต้กลุ่มใหญ่

ความซับซ้อน

แบบ	find หนึ่งครั้ง
ตรงไปตรงมา	O(N) ในกรณีแย่ที่สุด
path compression อย่างเดียว	เฉลี่ย O(log N) ต่อครั้งเมื่อทำหลายครั้ง แต่ครั้งเดียวยังเป็น O(N) ได้
union by size อย่างเดียว	O(log N) ทุกครั้ง
ทั้งสองอย่าง	เฉลี่ย O(α(N)) ต่อครั้ง

α(N) คือ inverse Ackermann function เป็นฟังก์ชันที่โตช้ามากจนมีค่าไม่เกิน 4 สำหรับ N ทุกค่าที่เก็บในคอมพิวเตอร์ได้ ในทางปฏิบัติจึงถือว่าเป็นเวลาคงที่ การพิสูจน์ยาวเกินขอบเขตของเอกสารนี้ สิ่งที่ต้องจำคือ union-find ที่มีทั้งสองเทคนิค ทำ N คนกับคำสั่ง Q ครั้งได้ใน O(N + Q α(N)) ซึ่งแทบเท่ากับแค่อ่านข้อมูล

เร็วขึ้นแค่ไหน

วัดบนโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 ระบบ Windows 11 คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks ข้อมูลคือข้อมูลแย่ที่สุดของแบบตรงไปตรงมา join 1 2 join 2 3 ไปจนถึง join N-1 N ให้ต้นไม้เป็นเส้นตรงยาว แล้วถาม Q ครั้งว่าคนที่ 1 กับคนหมายเลขที่กระจายไปทั่ว อยู่กลุ่มเดียวกันไหม จับเวลาด้วย clock() แบบหน้า 18.2 เฉพาะช่วง join กับ ask รันแต่ละแบบ 5 รอบ ตารางเป็นค่ากลาง

แบบ	N = Q = 10⁴ Code::Blocks	N = Q = 10⁴ `-O2`	N = Q = 10⁵ Code::Blocks	N = Q = 10⁵ `-O2`
ตรงไปตรงมา	0.387 วินาที	0.262 วินาที	39.0 วินาที (5 รอบอยู่ระหว่าง 34.5 ถึง 41.6)	22.8 วินาที (5 รอบอยู่ระหว่าง 21.4 ถึง 25.9)
path compression อย่างเดียว	0.001 วินาที	0.000 วินาที	พัง `0xC00000FD`	0.003 วินาที
union by size อย่างเดียว	0.000 วินาที	0.000 วินาที	0.003 วินาที	0.001 วินาที
ทั้งสองอย่าง	0.000 วินาที	0.000 วินาที	0.003 วินาที	0.001 วินาที

แบบตรงไปตรงมาที่ N เป็นแสนต้องเดินราว 1.5 × 10¹⁰ ก้าว ช้ากว่าแบบที่มีเทคนิคราว 13,000 เท่า (39.0 กับ 0.003 วินาทีแบบ Code::Blocks) ส่วน path compression อย่างเดียวเร็วพอๆ กับแบบอื่นในข้อมูลชุดนี้ เพราะ ask ครั้งแรกบีบทั้งเส้นให้แบนแล้ว แต่ ask ครั้งแรกนั้นต้อง recursion ลึกแสนชั้น แบบ Code::Blocks จึงพังด้วย stack overflow ส่วนแบบ -O2 รอดที่แสนแต่ไปพังที่ใหญ่กว่านั้น union by size ไม่เคยปล่อยให้ต้นไม้สูงเกิน 16 ชั้นตั้งแต่แรก จึงไม่มีปัญหานี้

ลองทำให้พัง

แบบที่ 1 path compression แบบ recursion โดยไม่มี union by size

ใช้โปรแกรม groups-compress ที่ไม่มี group_size ป้อนเส้นตรง N คนแบบเดียวกับข้อมูลเข้าข้างบน คือ join i i+1 ทุก i แล้วถาม ask 1 N รันจาก PowerShell ค่าละ 5 ครั้ง

N	Code::Blocks (`-Wall`)	`-O2`
10,000 20,000 และ 30,000	ผ่านทั้ง 5 ครั้ง	ผ่านทั้ง 5 ครั้ง
40,000 50,000 และ 100,000	พังทุกครั้ง	ผ่านทั้ง 5 ครั้ง
150,000 และ 200,000	พังทุกครั้ง	พังทุกครั้ง

ทุกครั้งที่พังได้

Process returned -1073741571 (0xC00000FD)

stack overflow แบบเดียวกับหน้า 26.3 find ครั้งแรกเรียกตัวเองลึกเท่าความยาวของเส้น โจทย์ union-find ให้ N ถึงแสนหรือสองแสนเป็นปกติ และชุดทดสอบที่ดีมีข้อมูลที่ทำให้ต้นไม้ยาวเสมอ โปรแกรม groups-size ที่มี union by size ด้วย ผ่านทุกขนาดที่ลองตั้งแต่ 10,000 ถึง 200,000 ทั้งสองแบบ เพราะ recursion ลึกไม่เกินความสูงของต้นไม้ ซึ่งไม่เกิน log₂ N ขั้น ถ้าอยากใช้ path compression อย่างเดียว ให้เขียน find เป็นลูปสองรอบ รอบแรกเดินหาหัวหน้า รอบที่สองเดินทางเดิมซ้ำแล้วให้ทุกคนชี้หัวหน้า

int find_root(int x)
{
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    while (parent[x] != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }
    return root;
}

แบบที่ 2 ตั้งชื่ออาเรย์ว่า size

หลายคนประกาศอาเรย์ไว้นอก main ให้ทุกฟังก์ชันใช้ได้ แล้วตั้งชื่อตามความหมายตรงๆ

int parent[100001];
int size[100001];

groups.cpp:22:9: error: reference to 'size' is ambiguous
   22 |     if (size[a] < size[b]) {
      |         ^~~~
groups.cpp:5:5: note:                 'int size [100001]'
    5 | int size[100001];
      |     ^~~~

ข้อความจริงยาว 78 บรรทัด error เดียวกันขึ้นซ้ำทุกจุดที่ใช้ size และแต่ละจุดมี note ชี้ไปที่ไฟล์ของ STL อีกหลายบรรทัด ที่ตัดมาคือ error ตัวแรกกับ note ที่ชี้ตัวแปรของเรา คำว่า ambiguous แปลว่ากำกวม เพราะตั้งแต่ C++17 ใน std มีฟังก์ชันชื่อ size อยู่แล้ว และ using namespace std; ดึงชื่อนั้นออกมาชนกับตัวแปรของเรา compiler จึงไม่รู้ว่าหมายถึงตัวไหน ชื่อ rank ที่เห็นบ่อยในโค้ด union-find ของคนอื่นก็ชนแบบเดียวกัน ตั้งชื่อให้ไม่ซ้ำ เช่น group_size หรือเก็บใน vector ที่ประกาศใน main

แบบที่ 3 รวมโดยไม่หาหัวหน้า

ในโปรแกรม groups-naive เขียน unite ให้สั้นลงเป็น parent[a] = b; เพราะคิดว่าให้ a ไปอยู่กลุ่มของ b ก็พอแล้ว

4 4
join 1 2
join 1 3
ask 2 3
ask 1 3

ask 2 3: no
ask 1 3: yes
parent: 3 2 3 4

2 กับ 3 ควรอยู่กลุ่มเดียวกัน เพราะทั้งคู่รวมกับ 1 มาแล้ว แต่ได้ no join 1 2 ตั้ง parent[1] = 2 แล้ว join 1 3 เขียนทับเป็น parent[1] = 3 1 จึงหลุดออกจากกลุ่มของ 2 ทิ้ง 2 ไว้คนเดียว การเขียนทับ parent ของคนที่ไม่ใช่หัวหน้าทำให้ต้นไม้ขาด ต้องต่อที่หัวหน้าเท่านั้น เพราะหัวหน้าเป็นคนเดียวในกลุ่มที่ parent ยังว่างอยู่

สรุป

union-find เก็บแต่ละกลุ่มเป็นต้นไม้ด้วยอาเรย์ parent หัวหน้ากลุ่มคือรากซึ่งชี้ตัวเอง สองคนอยู่กลุ่มเดียวกันเมื่อหัวหน้าเป็นคนเดียวกัน
รวมกลุ่มต้องต่อหัวหน้ากับหัวหน้าเสมอ
path compression ให้ทุกคนบนทางเดินชี้หัวหน้าตรงๆ union by size เอากลุ่มเล็กไปห้อยใต้กลุ่มใหญ่ ต้นไม้จึงสูงไม่เกิน log₂ N
ใช้ทั้งสองเทคนิค แต่ละครั้งเฉลี่ยเกือบคงที่ ข้อมูลเส้นตรงแสนคนเร็วกว่าแบบตรงไปตรงมาราว 13,000 เท่า
find แบบ recursion ที่ไม่มี union by size พังด้วย stack overflow บนเส้นตรงยาว และอย่าตั้งชื่อตัวแปรนอก main ว่า size หรือ rank