สมมติว่าเรามีตัวเลข n อาร์เรย์ที่เรียกว่า 'ภาษา' และอาร์เรย์ที่เรียกว่า 'มิตรภาพ' ดังนั้นจึงมี n ภาษาที่มีหมายเลขตั้งแต่ 1 ถึง n ภาษา[i] หมายถึงชุดของภาษาที่ผู้ใช้รู้จัก และมิตรภาพ[ i] ถือคู่ [ui, vi] หมายถึงมิตรภาพระหว่างผู้ใช้ ui และ vi เราสามารถเลือกภาษาหนึ่งและสอนให้กับผู้ใช้บางคนเพื่อให้เพื่อนทุกคนสามารถสื่อสารกันได้ เราต้องหาจำนวนผู้ใช้ขั้นต่ำที่จำเป็นในการสอน (สิ่งหนึ่งที่เราต้องจำไว้ว่ามิตรภาพไม่ใช่การถ่ายทอด ดังนั้น ถ้า x เป็นเพื่อนของ y และ y เป็นเพื่อนของ z ก็ไม่ได้หมายความว่า x เป็นเพื่อนของ z)
ดังนั้น หากการป้อนข้อมูลเป็นแบบ n =3 ภาษา =[[2],[1,3],[1,2],[3]] friendships =[[1,4],[1,2],[3 ,4],[2,3]] แล้วผลลัพธ์จะเป็น 2 เพราะเราต้องฝึกภาษา 3 ให้กับผู้ใช้ 1 และ 3 เนื่องจากมีผู้ใช้สองคนที่จะสอน ผลลัพธ์จึงเป็น 2
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- lang :=รายการชุดภาษาที่แตกต่างกันทั้งหมดที่ผู้ใช้รู้จัก
- not_comm :=ชุดใหม่
- สำหรับแต่ละคู่ a, b ในมิตรภาพ ทำ
- a :=a - 1
- b :=b - 1
- ถ้า lang[a] และ lang[b] ไม่ปะติดปะต่อกัน ดังนั้น
- แทรก a ลงใน not_comm
- แทรก b ลงใน not_comm
- ถ้า not_comm ว่างเปล่า
- คืน 0
- cnt :=แผนที่ว่างเปล่า
- สำหรับแต่ละคนใน not_comm ทำ
- เก็บความถี่ของ lang[บุคคล] และเก็บไว้ที่ cnt
- temp :=สูงสุดของรายการค่าทั้งหมดของ cnt
- ขนาดส่งคืนของ not_comm - ชั่วคราว
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
from collections import Counter def solve(n, languages, friendships): lang = [set(L) for L in languages] not_comm = set() for a,b in friendships: a -= 1 b -= 1 if lang[a].isdisjoint(lang[b]): not_comm.add(a) not_comm.add(b) if not not_comm: return 0 cnt = Counter() for person in not_comm: cnt.update(lang[person]) temp = max(cnt.values()) return len(not_comm) - temp n = 3 languages = [[2],[1,3],[1,2],[3]] friendships = [[1,4],[1,2],[3,4],[2,3]] print(solve(n, languages, friendships))
อินพุต
3, [[2],[1,3],[1,2],[3]], [[1,4],[1,2],[3,4],[2,3]]
ผลลัพธ์
2
