29.2 นับกลุ่ม ขนาดกลุ่ม และตรวจวงจร

union-find ในหน้า 29.1 ตอบได้แค่ว่าสองคนอยู่กลุ่มเดียวกันไหม แต่โจทย์มักถามต่อ เช่น ตอนนี้มีกี่กลุ่ม กลุ่มของคนนี้มีกี่คน กลุ่มที่ใหญ่ที่สุดมีกี่คน หรือถนนเส้นนี้ทำให้เกิดทางวนหรือเปล่า คำถามเหล่านี้ตอบได้ด้วยตัวแปรเพิ่มอีกสองสามตัว โดยไม่ทำให้ช้าลง หน้านี้รวมทุกอย่างไว้ในโปรแกรมเดียว แล้วเทียบกับการเดินกราฟด้วย BFS ของบทที่ 27 ว่าเมื่อไรควรใช้อะไร

โจทย์ถนนในหมู่บ้าน

หมู่บ้านมีบ้าน N หลัง ยังไม่มีถนนเลย เทศบาลสร้างถนนทีละเส้น ถนนวิ่งได้สองทาง ระหว่างนั้นมีคนถามเข้ามา คำสั่งมีสามแบบ

• road a b สร้างถนนระหว่างบ้าน a กับบ้าน b แล้วพิมพ์ว่าตอนนี้บ้านแบ่งเป็นกี่กลุ่มที่ไปมาหากันได้ และกลุ่มใหญ่สุดมีกี่หลัง
• same a b จากบ้าน a ขับรถไปบ้าน b ได้หรือยัง
• size a จากบ้าน a ขับไปได้กี่หลัง นับบ้าน a ด้วย

กลุ่มของบ้านที่ไปมาหากันได้ก็คือส่วนเชื่อมต่อ (connected component) ของกราฟในบทที่ 27 ถนนหนึ่งเส้นคือคำสั่ง join ในหน้า 29.1 สิ่งที่ต้องเพิ่มมีสามอย่าง

• จำนวนกลุ่ม เริ่มที่ N เพราะทุกหลังอยู่กลุ่มของตัวเอง ทุกครั้งที่ unite รวมสองกลุ่มที่ต่างกันได้จริง จำนวนกลุ่มลดลงหนึ่งพอดี ถ้าสองบ้านอยู่กลุ่มเดียวกันอยู่แล้ว จำนวนไม่เปลี่ยน unite จึงคืนค่า bool บอกว่ารวมจริงหรือไม่
• ขนาดกลุ่ม มีอยู่แล้วใน group_size ที่ใช้ทำ union by size แต่ค่าที่ถูกต้องอยู่ที่หัวหน้าเท่านั้น ต้องอ่าน group_size[find_root(a)]
• กลุ่มใหญ่สุด กลุ่มมีแต่รวมกันใหญ่ขึ้น ไม่เคยแยก ขนาดใหญ่สุดจึงเปลี่ยนได้เฉพาะตอนรวม เทียบกับขนาดของกลุ่มที่เพิ่งรวมเสร็จก็พอ

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

vector<int> parent, group_size;
int groups, largest;

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

bool unite(int a, int b)
{
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a == root_b) {
        return false; // (1)!
    }
    if (group_size[root_a] < group_size[root_b]) {
        swap(root_a, root_b);
    }
    parent[root_b] = root_a;
    group_size[root_a] += group_size[root_b];
    groups--; // (2)!
    largest = max(largest, group_size[root_a]); // (3)!
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    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;
    }
    groups = n;
    largest = 1;
    for (int k = 0; k < q; k++) {
        string op;
        cin >> op;
        if (op == "road") {
            int a, b;
            cin >> a >> b;
            unite(a, b);
            cout << "groups=" << groups << " largest=" << largest << '\n';
        } else if (op == "same") {
            int a, b;
            cin >> a >> b;
            cout << (find_root(a) == find_root(b) ? "yes" : "no") << '\n';
        } else {
            int a;
            cin >> a;
            cout << "size of " << a << " = " << group_size[find_root(a)] << '\n'; // (4)!
        }
    }
    return 0;
}

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

7 10
road 1 2
road 3 4
road 2 3
size 4
road 1 4
road 5 6
same 1 6
road 4 6
same 1 6
size 7

groups=6 largest=2
groups=5 largest=2
groups=4 largest=4
size of 4 = 4
groups=4 largest=4
groups=3 largest=4
no
groups=2 largest=6
yes
size of 7 = 1

ถนน 1-2 3-4 และ 2-3 ทำให้บ้าน 1 ถึง 4 เป็นกลุ่มเดียวกันขนาด 4 ถนน 1-4 ต่อสองบ้านที่ไปถึงกันได้อยู่แล้ว จำนวนกลุ่มจึงยังเป็น 4 เหมือนเดิม ถนนเส้นนี้ไม่ได้ช่วยให้ไปที่ใหม่ได้ แค่ทำให้เกิดทางวน ซึ่งเป็นเรื่องของหัวข้อตรวจวงจรข้างล่าง บ้าน 7 ไม่มีถนนเลย จึงอยู่กลุ่มขนาด 1 จนจบ ทุกคำสั่งใช้เวลาเท่ากับ find ไม่กี่ครั้ง ซึ่งเกือบคงที่ตามหน้า 29.1

BFS หรือ union-find

บทที่ 27 หาส่วนเชื่อมต่อด้วย BFS หรือ DFS ได้ใน O(N + M) เมื่อ N คือจำนวนโหนด และ M คือจำนวนเส้นเชื่อม ซึ่งบทที่ 27 เขียนเป็น O(V + E) สองวิธีนี้ไม่ได้แข่งกัน แต่เหมาะกับโจทย์คนละแบบ

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

วัดบนเครื่องเดียวกับหน้า 29.1 บ้าน N หลัง สร้างถนน N เส้นระหว่างบ้านสุ่ม และถามว่าสองบ้านสุ่มไปถึงกันได้ไหม N ครั้ง ถนนกับคำถามสลับกันแบบสุ่ม วิธีตรงไปตรงมาเก็บถนนเป็น adjacency list แล้ว BFS จากบ้าน a ทุกครั้งที่ถาม หยุดทันทีที่เจอบ้าน b ส่วนอีกวิธีคือโปรแกรม village ที่ตัดส่วนพิมพ์ออก จับเวลาเฉพาะช่วงทำคำสั่ง รันแต่ละแบบ 5 รอบ

ถนนสุ่มจำนวนเท่ากับบ้าน ทำให้บ้านส่วนใหญ่รวมเป็นกลุ่มใหญ่กลุ่มเดียว แต่สองบ้านสุ่มอยู่คนละกลุ่มเป็นส่วนมาก ข้อมูลชุดแสนหลังตอบ yes แค่ 16009 ครั้งจากแสนคำถาม คำถามที่ตอบ no ทำให้ BFS ต้องเดินทั่วกลุ่มของ a จนหมดก่อนจะรู้ว่าไม่เจอ งานต่อคำถามจึงโตตาม N และงานรวมโตราว N² ข้อมูลใหญ่ขึ้นสิบเท่า BFS ช้าลงราว 140 เท่าทั้งสองแบบ ส่วน union-find ยังใช้ไม่ถึงหนึ่งในร้อยวินาที

ตรวจวงจรในกราฟไม่มีทิศทาง

ถนน 1-4 ในโปรแกรม village ไม่ได้รวมกลุ่มใหม่ เพราะบ้าน 1 กับ 4 ไปถึงกันได้อยู่แล้วผ่าน 2 กับ 3 พอเพิ่มถนนเส้นนี้ ก็เกิดทางวน 1-2-3-4-1 ขึ้น ซึ่งคือวงจร (cycle) ตามนิยามในหน้า 27.1 หน้า 27.2 ตรวจวงจรด้วย DFS ไปแล้ว คือเจอโหนดที่จดแล้วซึ่งไม่ใช่พ่อ แต่ต้องมีเส้นเชื่อมครบก่อนแล้วค่อยเดิน union-find ตรวจได้ทีละเส้นตอนที่เส้นทยอยเข้ามา หลักคิดคือ

unite ที่คืน false คือสัญญาณนี้พอดี โปรแกรมนี้อ่านเส้นเชื่อมของกราฟ แล้วบอกว่าเส้นไหนปิดวงจรบ้าง

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

vector<int> parent, group_size;

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

bool unite(int a, int b)
{
    int root_a = find_root(a);
    int root_b = find_root(b);
    if (root_a == root_b) {
        return false;
    }
    if (group_size[root_a] < group_size[root_b]) {
        swap(root_a, root_b);
    }
    parent[root_b] = root_a;
    group_size[root_a] += group_size[root_b];
    return true;
}

int main()
{
    int n, m;
    cin >> n >> m;
    parent.resize(n + 1);
    group_size.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    int extra = 0;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        if (!unite(a, b)) { // (1)!
            cout << "edge " << i << " (" << a << ", " << b << ") closes a cycle" << '\n';
            extra++;
        }
    }
    cout << "edges that close a cycle: " << extra << '\n';
    cout << (extra == 0 ? "forest" : "has a cycle") << '\n';
    return 0;
}

1. รวมไม่ได้เพราะอยู่กลุ่มเดียวกันแล้ว เส้นนี้จึงปิดวงจร ถ้ารวมได้ unite ก็รวมให้ในบรรทัดเดียวกัน

6 7
1 2
2 3
4 5
3 1
5 6
6 4
2 5

edge 4 (3, 1) closes a cycle
edge 6 (6, 4) closes a cycle
edges that close a cycle: 2
has a cycle

เส้นที่ 4 ต่อ 3 กับ 1 ซึ่งถึงกันอยู่แล้วผ่าน 2 เส้นที่ 6 ต่อ 6 กับ 4 ซึ่งถึงกันอยู่แล้วผ่าน 5 ส่วนเส้นที่ 7 ต่อสองสามเหลี่ยมที่ยังไม่ถึงกัน จึงไม่ปิดวงจร แม้จะมาทีหลังสุดก็ตาม สังเกตว่าเส้นที่ถูกรายงานขึ้นกับลำดับที่ใส่ ถ้าสลับให้เส้น 3-1 มาก่อนเส้น 2-3 เส้นที่ถูกรายงานจะเป็น 2-3 แทน แต่จำนวนเส้นที่ปิดวงจรเท่าเดิมเสมอ เพราะ

จำนวนเส้นที่ปิดวงจร = M - (N - C)

เมื่อ C คือจำนวนกลุ่มตอนจบ ทุกเส้นที่รวมกลุ่มได้ทำให้จำนวนกลุ่มลดลงหนึ่ง จาก N ลงมาเหลือ C จึงมีเส้นที่รวมได้ N - C เส้นพอดี เส้นที่เหลือปิดวงจรทั้งหมด ตัวอย่างนี้ได้ 7 - (6 - 1) = 2 ผลที่ตามมาอีกข้อคือ กราฟที่มี N โหนด ต่อถึงกันหมด และไม่มีวงจร ต้องมีเส้นเชื่อม N - 1 เส้นพอดี ซึ่งก็คือต้นไม้ที่จะใช้ในหน้า 29.3

เส้นที่ต่อโหนดกับตัวเอง เช่น 2 2 และเส้นที่ซ้ำกับเส้นเดิม ถูกนับเป็นเส้นที่ปิดวงจรด้วย ลองป้อน 3 3 ตามด้วยเส้น 1 2 2 2 1 2 โปรแกรมรายงานเส้นที่ 2 และ 3 ถ้าโจทย์นับแบบอื่นต้องอ่านให้ดี

ลองทำให้พัง

แบบที่ 1 ไม่เช็กว่าอยู่กลุ่มเดียวกันแล้ว

ในโปรแกรม village ลบสามบรรทัดที่คืน false เมื่อ root_a == root_b ออก เพราะคิดว่าต่อหัวหน้ากับตัวเองก็ไม่เสียหาย ป้อนข้อมูลเข้าชุดเดิม

groups=6 largest=2
groups=5 largest=2
groups=4 largest=4
size of 4 = 4
groups=3 largest=8
groups=2 largest=8
no
groups=1 largest=10
yes
size of 7 = 1

ถนน 1-4 ทำให้จำนวนกลุ่มลดจาก 4 เป็น 3 และกลุ่มใหญ่สุดกลายเป็น 8 หลัง ทั้งที่หมู่บ้านมีแค่ 7 หลัง ตอนจบโปรแกรมบอกว่าเหลือกลุ่มเดียว แต่บ้าน 7 ยังไม่มีถนนเลย parent[root_b] = root_a ที่หัวหน้าเป็นคนเดียวกันไม่ทำให้ต้นไม้เสีย แต่ group_size[root_a] += group_size[root_b] บวกกลุ่มเข้ากับตัวเองจนขนาดเป็นสองเท่า และ groups-- นับการรวมที่ไม่ได้เกิดขึ้นจริง ชุดทดสอบที่ไม่มีถนนซ้ำหรือถนนที่ทำให้วนจะผ่าน แล้วตกในชุดที่มี

แบบที่ 2 อ่านขนาดที่ตัวเองแทนที่หัวหน้า

ในโปรแกรม village เปลี่ยน group_size[find_root(a)] เป็น group_size[a]

groups=6 largest=2
groups=5 largest=2
groups=4 largest=4
size of 4 = 1
groups=4 largest=4
groups=3 largest=4
no
groups=2 largest=6
yes
size of 7 = 1

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

สรุป

• จำนวนกลุ่มเริ่มที่ N และลดลงหนึ่งทุกครั้งที่ unite รวมได้จริง ให้ unite คืน bool
• ขนาดกลุ่มอ่านที่หัวหน้า group_size[find_root(x)] กลุ่มใหญ่สุดอัปเดตตอนรวม
• เส้นเชื่อมทยอยเพิ่มและมีคำถามแทรก ใช้ union-find ถ้าต้องรู้เส้นทางหรือระยะทาง ใช้ BFS หรือ DFS
• เส้น a-b ที่ a กับ b อยู่กลุ่มเดียวกันแล้วคือเส้นที่ปิดวงจร มีทั้งหมด M - (N - C) เส้น ใช้ได้กับกราฟไม่มีทิศทางเท่านั้น
• union-find แยกกลุ่มไม่ได้ ถ้าโจทย์มีแต่การลบและรู้คำสั่งทั้งหมดก่อน ให้ทำย้อนหลัง