สมมติว่าเรามี star graph แบบไม่มีทิศทางที่มี n โหนดตั้งชื่อ 1 ถึง n ตามที่รู้ star graph คือกราฟที่มีโหนดศูนย์กลางหนึ่งตัว และมีเส้นขอบ n - 1 เส้นเชื่อมโหนดศูนย์กลางกับโหนดอื่นๆ ทุกตัว เราต้องหาศูนย์กลางของ star graph ที่กำหนด
เช่น ถ้าอินพุตเป็นดังภาพ ผลลัพธ์จะเป็น 3 เพราะ 3 อยู่ตรงกลาง
วิธีแก้ปัญหา
- seen := เซตใหม่
- สำหรับแต่ละเส้นขอบ (u,v) ใน graph:
- ถ้า u อยู่ใน seen: return u
- ถ้า v อยู่ใน seen: return v
- เพิ่ม u ลง seen
- เพิ่ม v ลง seen
ตัวอย่าง
def solve(graph):
seen = set()
for u, v in graph:
if u in seen:
return u
if v in seen:
return v
seen.add(u)
seen.add(v)
graph = [(1,3),(2,3),(4,3),(5,3),(6,3)]
print(solve(graph))
อินพุต
[(1,3),(2,3),(4,3),(5,3),(6,3)]
เอาต์พุต
3
