1615-maximal-network-rank.py

from collections import defaultdict
from typing import List


class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        maxRank = 0
        adj = defaultdict(set)

        for road in roads:
            adj[road[0]].add(road[1])
            adj[road[1]].add(road[0])

        for node1 in range(n):
            for node2 in range(node1 + 1, n):
                currentRank = len(adj[node1]) + len(adj[node2])
                if node2 in adj[node1]:
                    currentRank -= 1
                maxRank = max(maxRank, currentRank)
        return maxRank