LeetCode 1615: Classificação máxima da rede

Question

Estou postando uma solução para "Maximal Network Rank" do LeetCode. Se você gostaria de revisar, por favor, faça-o. Obrigado!

Problema

Há uma infraestrutura de n cidades com algum número de estradas conectando essas cidades. Cada estrada [i] = [ai, bi] indica que há uma estrada bidirecional entre as cidades ai e bi.

A classificação da rede de duas cidades diferentes é definida como o número total de estradas diretamente conectadas a qualquer uma das cidades. Se uma estrada estiver conectada diretamente a ambas as cidades, ela será contada apenas uma vez.

A classificação de rede máxima da infraestrutura é a classificação de rede máxima de todos os pares de cidades diferentes.

Dado o inteiro n e as estradas da matriz, retorne a classificação máxima da rede de toda a infraestrutura.

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        indegrees = collections.defaultdict(list)
        for i in range(n):
            for a, b in roads:
                if i == a:
                    indegrees[i].append(f'{i}-{b}')
                    indegrees[i].append(f'{b}-{i}')
                if i == b:
                    indegrees[i].append(f'{i}-{a}')
                    indegrees[i].append(f'{a}-{i}')

        max_net = 0
        for i in range(n):
            for j in range(n):
                if f'{i}-{j}' or f'{j}-{i}' in indegrees[i]:
                    net = len(set(indegrees[i] + indegrees[j])) // 2
                    max_net = max(max_net, net)

        return max_net

Answer 1

Evite converter estruturas de dados em string desnecessariamente

Basta armazenar tuplas de valores em indegreesvez de strings:

if i == a:
    indegrees[i].append((i, b))
    indegrees[i].append((b, i))

Repita as chaves indegreesdiretamente

Neste trecho de código:

for i in range(n):
    for j in range(n):
        if f'{i}-{j}' or f'{j}-{i}' in indegrees[i]:
            ...

O que você está basicamente dizendo é: para cada par possível de inteiros, verifique se ele está presente indegreese, em caso afirmativo, faça algo com ele. Isso é muito ineficiente se houver apenas alguns elementos indegrees. Por que não apenas iterar nas chaves de indegrees? Você pode fazer isso com strings, mas então você tem que analisar cada chave de volta em dois valores, se você armazenar tuplas, torna-se realmente simples:

for i, j in indegrees:
    ...