โปรแกรมหา maximal network rank ใน Python

ปัญหา

มี n เมือง และถนน roads[i] = [u,v] network rank ของคู่เมือง = จำนวนถนนที่เชื่อมต่อกับเมืองใดเมืองหนึ่ง (ถนนที่เชื่อมทั้งสองนับ 1 ครั้ง) maximal network rank = ค่าสูงสุดของทุกคู่

ตัวอย่าง

roads = [(0,1),(0,3),(1,2),(1,3),(2,3),(2,4)] → 5 (เมือง 1 และ 2 มี rank 5)

ขั้นตอนการแก้ปัญหา

1. nodes := set(), s := set(), d := defaultdict(int)
2. สำหรับ (x,y) ใน roads:
   • nodes.add(x), nodes.add(y)
   • d[x]+=1, d[y]+=1
   • s.add((x,y))
3. l := sorted(range(n), key=lambda x: d[x], reverse=True)
4. threshold := min(d[l[0]], d[l[1]])
5. วนคู่ (i,j) ใน l:
   • ถ้า d[l[j]] < threshold: break
   • curr := d[l[i]] + d[l[j]]
   • ถ้า (l[i],l[j]) in s: curr -= 1
   • ans = max(ans, curr)
6. คืน ans

การนำไปใช้งาน (Python)

from collections import defaultdict
def solve(roads):
    nodes = set()
    s = set()
    d = defaultdict(int)
    for x, y in roads:
        nodes.update([x, y])
        d[x] += 1
        d[y] += 1
        s.add((x, y))
    ans = 0
    n = len(nodes)
    l = list(range(n))
    l.sort(key=lambda x: d[x], reverse=True)
    threshold = min(d[l[0]], d[l[1]])
    for i in range(len(l) - 1):
        for j in range(i + 1, len(l)):
            if d[l[j]] < threshold:
                break
            curr = d[l[i]] + d[l[j]]
            if (l[i], l[j]) in s or (l[j], l[i]) in s:
                curr -= 1
            ans = max(ans, curr)
    return ans

roads = [(0,1),(0,3),(1,2),(1,3),(2,3),(2,4)]
print(solve(roads))

อินพุต

[(0,1),(0,3),(1,2),(1,3),(2,3),(2,4)]

เอาต์พุต

5