Chương trình tìm hạng mạng tối đa trong Python

Cho n thành phố và các đường 2 chiều roads[i]=[u,v]. Hạng mạng (network rank) của cặp thành phố = tổng bậc của 2 thành phố, trừ 1 nếu có đường trực tiếp giữa chúng. Hạng mạng tối đa = max hạng mạng của mọi cặp.

Ví dụ: đồ thị cho trước → 5 (cặp 1 và 2).

Giải thuật (Tính bậc + kiểm tra cặp top)

1. Tính bậc d[u] cho mỗi đỉnh, set s lưu các cạnh.
2. Sắp xếp đỉnh theo bậc giảm dần.
3. threshold = min(d[top1], d[top2]).
4. Duyệt cặp (i,j) trong danh sách đã sắp xếp:
   • Nếu d[j] < threshold: break (các cặp sau không thể tốt hơn).
   • curr = d[i] + d[j] - (1 if (i,j) in s else 0).
   • Cập nhật ans = max(ans, curr).

Ví dụ minh họa

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))

Đầu vào

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

Đầu ra

5