Thailand OI: คอมพิวเตอร์โอลิมปิก ประเทศไทย

Union-Find Data Structure คือ โครงสร้างข้อมูลแบบหนึ่ง ที่เอาไว้ใช้สำหรับข้อมูลที่อยู่ในรูป Disjoint Set

Disjoint Set คืออะไร

Disjoint Set ก็คือ เวลาเรามี Universe ที่ประกอบด้วยสมาชิกจำนวนหนึ่ง แล้วเราแบ่งมันเป็น set ย่อยๆหลายๆเซต ที่มีคุณสมบัติดังนี้

• ถ้าหยิบมาสองเซตย่อยใดๆ จะ intersection กันได้เซตว่าง (สองเซตใดๆไม่มีสมาชิกซ้ำกัน)
• ทุกเซต union กันได้ Universe (ต้องมีสมาชิกครบ Universe)

Union-Find Data Structure

เป็น data structure ที่ไว้สำหรับเก็บ disjoint set ส่วนoperation ที่เราทำได้ คือ

• union นั่นคือ นำสองเซตมารวมกันเป็นเซตเดียว
• find นั่นคือ หาว่าสมาชิกตัวนี้ อยู่ในเซตใด โดยเรามักจะกำหนดสมาชิกตัวใดตัวหนึ่งเป็น “หัว” ของแต่ละเซต ดังนั้น เวลาเราถามว่า สมาชิกนี้อยู่เซตใด เราจะตอบตัวที่เป็น”หัว”ของมัน

ดังนั้น เราสามารถใช้คำสั่ง find ในการดูว่า สมาชิกสองตัวอยู่ในเซตเดียวกันหรือไม่ โดยหา “หัว” ของสมาชิกทั้งสอง ถ้า”หัว”เป็นตัวเดียวกัน แสดงว่า สมาชิกทั้งสองอยู่เซตเดียวกัน

ตัวอย่างการ Union

อย่างเช่น มีเซตอยู่สี่เซต คือ {1} {2} {3} {4} และ Universe คือ {1,2,3,4} จะสังเกตว่า สองเซตใดๆ intersection กันได้เซตว่าง (หมายความว่า ไม่มีตัวซ้ำ) และทุกเซต union กันได้ universe (ไม่มีตัวใดไม่อยู่ในเซต)

• {1} {2} {3} {4}
• {1} union {2}
• {1,2} {3} {4}
• {1,2} union {4}
• {1,2,4} {3}
• {1,2,4} union {3}
• {1,2,3,4}

ลักษณะของ Union-Find Data Structure แบบ Disjoint-set forests

แต่ละเซตจะมีลักษณะเป็น tree ที่ node ใน tree แต่ละ node แทนสมาชิกแต่ละตัวในเซต ทุก node จะชี้ไปหาพ่อของมัน และตัวบนสุด (ตัวที่เป็น”หัว”ของเซตนี้) จะชี้ไปที่ตัวเอง

การ find

เมื่อเรามี node ที่เราต้องการหา “หัว” ก็ค่อยๆไต่ลูกศรขึ้นไปหาพ่อของมันไปเรื่อยๆ จนถึงตัวบนสุด ก็จะได้ “หัว” ของเซต เช่นในรูปด้านบน สมมติเราต้องการหา “หัว” ของ 7 เราก็จะค่อยๆไต่ขึ้นไปที่ 5 และจบที่ 3

int findhead(int x)
{
    if(x!=parent[x])
        return findhead(parent[x]);
    else
        return x;
}

การ union

เราก็ดูก่อนว่าสองเซตเป็นเซตเดียวกันหรือไม่ โดยการเปรียบเทียบ “หัว” ของทั้งสองเซต สมมติว่าทั้งสองเซตเป็นคนละเซต มองในรูป tree 2 ต้น เราก็นำ”หัว”ของ tree ต้นใดก็ได้ ไปเชื่อมกับ”หัว”ของ tree อีกต้นหนึ่ง ดังภาพ

แต่บางกรณี มันก็จะรันช้ามากสิ?

เช่นกรณีที่ find แต่ละครั้งต้องวิ่งเส้นทางยาวๆ ใน tree ขนาดใหญ่?

เราจะมีวิธี optimize ให้รันเร็วขึ้นสองวิธี ดังนี้

การเลือกลำดับการ union

เราจะเลือก tree ต้นที่เล็กกว่า เอาไปต่อกับ “หัว” ของ tree ต้นที่ใหญ่กว่าเสมอ โดยเราจะนิยามความใหญ่โดยการกำหนด “rank” ให้แต่ละ tree

ในตอนเริ่มต้น tree ที่มีสมาชิกเพียงตัวเดียวจะมี rank = 0 และเมื่อเอา tree ที่ rank เท่ากันมา union กัน tree ที่ได้ออกมาจะมี rank เพิ่มขึ้นหนึ่ง ดังโค้ด

void unionset(int a, int b)
{
    int heada = findhead(a), headb=findhead(b);
    if(heada==headb)
        return;
    if(rank[heada]>rank[headb])
        head[headb]=heada;
    else if(rank[headb]>rank[heada])
        head[heada]=headb;
    else
    {
        head[headb]=heada;
        rank[heada]++;
    }
}

การทำ Path Compression

เวลาที่เรา find แต่ละครั้ง เราจะต้องวิ่งเส้นทางลูกศรขึ้นไปจนถึงตัวบนสุด

Path Compression จะประหยัดเวลาในการวิ่งเส้นทางนี้ โดยการ พอวิ่งไปถึงตัวใด ก็เปลี่ยนลูกศรของมันให้ไปที่ “หัว” ของทั้งเซต

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

ถ้าจะ optimize กว่านี้อีก ก็เปลี่ยนจากการ recursive มาเป็นการใช้ลูป for แทน

ด้วยการ optimize สองอย่างนี้ จะทำให้เวลารันลดลงเหลือประมาณ O(n) (คิดแบบ amortized - จะพูดถึงในภายหลัง)

การนำไปใช้

• Kruskal’s Minimum Spanning Tree Algorithm

ใช้ในการเก็บ Tree ย่อยๆแต่ละต้น โดยเริ่มแรกแต่ละ Tree มีเพียง node เดียว แล้วก็ union ขึ้นไปเรื่อยๆ

• โจทย์ข้อฟองนม
• โจทย์ข้อนายพล
• อื่นๆ

หากมีข้อสงสัย…

1. ลองอ่านอีกรอบดู หรือ
2. ทิ้งคอมเมนท์ไว้ก็ได้ค่ะ