Maximal Network Rank — LeetCode 1615 Python Solution

The problem

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi.

Example

Input

n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]

Output

4

Explanation

The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.

Python solution

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        g = [[0] * n for _ in range(n)]
        cnt = [0] * n
        for a, b in roads:
            g[a][b] = g[b][a] = 1
            cnt[a] += 1
            cnt[b] += 1
        return max(cnt[a] + cnt[b] - g[a][b] for a in range(n) for b in range(a + 1, n))

Complexity

Pattern: Depth-First Search

Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 1615. Maximal Network Rank is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Graph.

The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.

Related problems