Busiest Pair of Cities

Medium

A country has city_count cities numbered from 0 to city_count - 1. Each roads[i] = [a, b] is a two-way road between cities a and b; any two cities are joined by at most one road. The load of a pair of different cities is the number of roads that touch at least one of them. A road that runs directly between the two is counted once. Return the largest load over all pairs of cities.

Example 1

city_count=5, roads=[[0, 1], [0, 2], [0, 3], [3, 4]] → 4

City 0 has 3 roads and city 3 has 2, one of which (0–3) they share. Together that is 3 + 2 − 1 = 4.

Example 2

city_count=6, roads=[[0, 1], [0, 2], [3, 4], [3, 5]] → 4

The cities need not be connected: 0 and 3 have two roads each and share none, so 4.

Example 3

city_count=3, roads=[] → 0

Constraints

2 ≤ city_count ≤ 200
0 ≤ len(roads) ≤ city_count · (city_count − 1) / 2
roads[i] = [a, b], 0 ≤ a, b < city_count, a ≠ b
Any two cities share at most one road

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph

Similar problems

Module Build Order Medium Course Enrollment Queue Medium Do the Links Form a Tree Medium Best Roots for a Tree Medium Isolated Groups in a Network Medium

Input

city_count=5, roads=[[0, 1], [0, 2], [0, 3], [3, 4]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 42 tests on the server, hidden ones included.