Number of Provinces

Q: Qual é a complexidade de tempo de Número de Províncias?

O(n²) com uma busca em grafo ou union-find, porque ambos leem cada entrada da matriz n × n uma vez. Union-find acrescenta um fator α(n), a função inversa de Ackermann, que é no máximo 4 para qualquer entrada real. O espaço extra é O(n) para as sinalizações de visitado ou para os arrays de pai e de posto.

Q: Você deve usar DFS, BFS ou union-find para o problema Number of Provinces?

Os três retornam a mesma contagem em tempo O(n²). DFS ou BFS são os mais rápidos de escrever quando a matriz inteira é fornecida de uma só vez. Union-find é a melhor ferramenta quando as estradas chegam uma por uma ou quando você também precisa responder se duas cidades compartilham uma província, porque lida com cada estrada e cada pergunta em tempo quase constante, sem uma nova busca.

Q: O que a compressão de caminho e a união por rank fazem na estrutura union-find?

A união por rank anexa a árvore mais curta sob a mais alta quando dois grupos se unem, o que mantém cada árvore com altura de no máximo log n. A compressão de caminho faz com que cada nó pelo qual find passa aponte diretamente para a raiz, então buscas posteriores a partir desses nós levam uma etapa. Com ambos, qualquer sequência de m operações custa O(m α(n)), o que se comporta como tempo linear.

Q: Qual é a diferença entre Número de Províncias e Número de Ilhas?

Ambos contam componentes conectados. Em Number of Islands, o grafo é uma grade, cada quadrado tem no máximo quatro vizinhos, e o trabalho é O(rows × cols). Aqui, o grafo é fornecido como uma matriz de adjacência: qualquer cidade pode se conectar a qualquer outra, e você lê uma linha inteira com n entradas para listar os vizinhos de uma cidade.

MédioUnion-find Grafos

+10

Há n cidades, numeradas de 0 a n-1. Você recebe uma matriz n × n chamada isConnected, representada como uma lista de linhas: isConnected[i][j] é 1 quando uma estrada liga diretamente a cidade i à cidade j, e 0 quando não liga. As estradas funcionam nos dois sentidos, portanto a matriz é simétrica, e toda cidade é considerada ligada a si mesma.

Uma província é um grupo de cidades que conseguem alcançar umas às outras, diretamente ou por meio de outras cidades, sem que nenhuma estrada saia do grupo. Retorne o número de províncias.

Função

findCircleNum(isConnected: integer-2d-array) → integer

isConnectedinteger-2d-array: a matriz n × n, 1 quando uma estrada liga duas cidades diretamente
Retornainteger: o número de províncias

Restrições

1 ≤ n ≤ 150, em que n = isConnected.length
isConnected[i].length = n
isConnected[i][j] é 0 ou 1
isConnected[i][i] = 1
isConnected[i][j] = isConnected[j][i]

Exemplos

Entrada: isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
Saída: 2
Explicação: A cidade 0 tem uma estrada até a cidade 3, e a cidade 1 tem uma estrada até a cidade 2. Nenhuma estrada conecta os dois pares, então há 2 províncias.

+15 testes ocultos ao enviar

Para ir além

Cada estrada agora é aberta em um determinado dia. Você consegue encontrar o primeiro dia em que todas as cidades pertencem a uma única província?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A matriz é a matriz de adjacência de um grafo não direcionado: as cidades são nós, e um 1 na linha i, coluna j representa uma aresta. Uma província é um componente conectado, então a resposta é o número de componentes. A armadilha é a conexão por meio de uma terceira cidade: um 0 entre duas cidades não as coloca em províncias diferentes. Uma busca a partir de cada cidade não visitada, ou uma estrutura union-find que une as duas extremidades de cada aresta, conta os componentes em O(n²), o tamanho da própria matriz.

Busca em profundidade a partir de cada cidade não visitada

Intuição

Percorra as cidades em ordem. Quando encontrar uma cidade que nenhuma busca anterior marcou, ela não pode pertencer a uma província que você já contou, porque cada busca marca toda a sua província. Portanto, incremente a contagem e, em seguida, marque todas as cidades que esta consegue alcançar.

Para encontrá-las, mantenha uma pilha. Remova uma cidade da pilha, leia sua linha da matriz e adicione à pilha todas as cidades com um 1 nessa linha que ainda não foram marcadas, marcando-as ao adicioná-las. No segundo exemplo, a busca a partir da cidade 0 adiciona a cidade 1 à pilha, e a linha da cidade 1 então adiciona a cidade 2, embora a linha 0 tenha um 0 para a cidade 2. Seguir as linhas dessa maneira é o que permite encontrar cidades conectadas apenas por meio de outras.

Cada cidade é removida da pilha uma vez, e removê-la significa ler sua linha com n entradas, então o tempo total é O(n²): você lê a matriz uma vez. As marcações e a pilha armazenam no máximo n cidades, então o espaço extra é O(n).

Uma busca recursiva fica mais organizada, mas, em uma província com o formato de uma única linha longa, as chamadas são aninhadas uma vez por cidade. Com n = 150, isso é seguro; o mesmo código em um grafo com 10^5 nós estoura a pilha de chamadas, então vale a pena manter o hábito de usar uma pilha explícita.

Algoritmo

Crie uma flag de visitado para cada cidade e defina a contagem como 0.
Percorra as cidades em ordem e pule qualquer cidade já visitada.
Para uma cidade não visitada, some 1 à contagem, marque-a como visitada e coloque-a em uma pilha.
Enquanto houver cidades na pilha, retire uma e coloque na pilha todas as cidades em sua linha que tenham 1 e ainda não tenham sido visitadas, marcando cada uma ao colocá-la.
Retorne a contagem.

def findCircleNum(isConnected):
    n = len(isConnected)
    seen = [False] * n
    provinces = 0
    for start in range(n):
        if seen[start]:
            continue
        # Nobody reached this city from an earlier province, so it starts a new one.
        provinces += 1
        seen[start] = True
        stack = [start]
        while stack:
            city = stack.pop()
            row = isConnected[city]
            for other in range(n):
                # Mark a city when you push it, so it is never pushed twice.
                if row[other] == 1 and not seen[other]:
                    seen[other] = True
                    stack.append(other)
    return provinces

Union-find com compressão de caminho e união por rank

Intuição

Inverta a pergunta. Comece com n províncias, uma por cidade. Cada 1 na matriz indica que duas cidades pertencem ao mesmo grupo: se ainda estiverem em grupos diferentes, una os grupos, e a contagem diminui em um. Depois da última estrada, a contagem é a resposta. Você só precisa das entradas acima da diagonal, porque a matriz é simétrica e a diagonal liga uma cidade a si mesma. No segundo exemplo, a contagem começa em 5. O 1 em (0, 1) une as cidades 0 e 1 (restam 4), e o 1 em (1, 2) constata que a cidade 1 pertence ao grupo da cidade 0 e acrescenta a cidade 2 a ele (restam 3). As cidades 3 e 4 não têm nenhum 1 acima da diagonal, então a resposta é 3.

Uma estrutura union-find, também chamada de união de conjuntos disjuntos, armazena cada grupo como uma árvore. parent[c] aponta um nível acima, e a cidade no topo, cujo pai é ela mesma, é a raiz do grupo. Duas cidades estão no mesmo grupo exatamente quando find percorre os caminhos de ambas até a mesma raiz. Para unir dois grupos, aponte uma raiz para a outra.

Duas regras mantêm as árvores baixas. União por rank pendura a árvore mais baixa sob a mais alta, de modo que uma árvore de altura h contenha pelo menos 2^h cidades e nenhum caminho tenha mais de log n níveis. Compressão de caminho vai além: depois que find localiza a raiz, ele aponta diretamente para essa raiz cada cidade pela qual passou, de modo que a próxima busca a partir de qualquer uma delas leve um único passo. Sem nenhuma dessas regras, unir as cidades de uma cadeia longa em uma ordem desfavorável cria uma árvore que é um único caminho, e cada find percorre O(n) passos.

Com as duas regras, cada find custa O(α(n)) amortizado, em que α é a função inversa de Ackermann, que permanece no máximo em 4 para qualquer n que um computador possa armazenar. A leitura da matriz ainda custa O(n²), então esse é o custo total, e os arrays parent e rank ocupam O(n) espaço. A estrutura se justifica quando as estradas chegam uma de cada vez: ela mantém a contagem atualizada após cada nova estrada sem fazer outra busca.

Algoritmo

Defina parent[c] = c e rank[c] = 0 para cada cidade, e o contador como n.
Para cada par i < j com isConnected[i][j] = 1, encontre as raízes de i e j.
Em find, suba até a raiz; em seguida, percorra novamente o mesmo caminho e aponte cada cidade nele diretamente para a raiz.
Se as raízes forem diferentes, anexe a raiz de menor rank à outra, aumente o rank em 1 em caso de empate e subtraia 1 do contador.
Retorne o contador.

def findCircleNum(isConnected):
    n = len(isConnected)
    parent = list(range(n))
    rank = [0] * n

    def find(city):
        root = city
        while parent[root] != root:
            root = parent[root]
        # Path compression: point every city on the way straight at the root.
        while parent[city] != root:
            up = parent[city]
            parent[city] = root
            city = up
        return root

    provinces = n
    for i in range(n):
        for j in range(i + 1, n):  # the matrix is symmetric, so the upper half is enough
            if isConnected[i][j] == 1:
                a, b = find(i), find(j)
                if a == b:
                    continue
                # Union by rank: hang the shorter tree under the taller one.
                if rank[a] < rank[b]:
                    a, b = b, a
                parent[b] = a
                if rank[a] == rank[b]:
                    rank[a] += 1
                # Two provinces just became one.
                provinces -= 1
    return provinces

Armadilhas e casos extremos

A maioria das respostas erradas trata um 0 como prova de que duas cidades estão separadas ou conta algo que não sejam componentes.

Verificar apenas as estradas diretas. As cidades 0 e 2 no segundo exemplo têm um 0 entre elas e ainda assim compartilham uma província por meio da cidade 1. Qualquer contagem baseada apenas em estradas diretas não percebe isso; contar as linhas distintas, por exemplo, resulta em 5 em vez de 3.
Contar os 1s e dividir por dois. Isso conta estradas, não províncias: três cidades que se conectam entre si têm três estradas e uma província.
Em union-find, diminuir a contagem a cada 1, em vez de apenas quando as duas raízes são diferentes. Uma estrada dentro de um grupo que já foi unido não deve alterar a contagem.
Comparar os pais em vez das raízes. parent[i] == parent[j] pode ser falso para duas cidades no mesmo grupo quando uma está mais abaixo na árvore; sempre compare find(i) com find(j).
Vincular a própria cidade j em vez da raiz dela, como em parent[j] = find(i). Se j já fazia parte de um grupo, o restante desse grupo fica de fora da união.
Recursão em grafos grandes. Uma busca recursiva, ou um find recursivo sem união por rank, percorre um nível por cidade em um grafo em forma de cadeia. Isso funciona para 150 cidades, mas causa estouro de pilha com 10^5.

Perguntas frequentes4

Qual é a complexidade de tempo de Número de Províncias?

O(n²) com uma busca em grafo ou union-find, porque ambos leem cada entrada da matriz n × n uma vez. Union-find acrescenta um fator α(n), a função inversa de Ackermann, que é no máximo 4 para qualquer entrada real. O espaço extra é O(n) para as sinalizações de visitado ou para os arrays de pai e de posto.

Você deve usar DFS, BFS ou union-find para o problema Number of Provinces?

Os três retornam a mesma contagem em tempo O(n²). DFS ou BFS são os mais rápidos de escrever quando a matriz inteira é fornecida de uma só vez. Union-find é a melhor ferramenta quando as estradas chegam uma por uma ou quando você também precisa responder se duas cidades compartilham uma província, porque lida com cada estrada e cada pergunta em tempo quase constante, sem uma nova busca.

O que a compressão de caminho e a união por rank fazem na estrutura union-find?

A união por rank anexa a árvore mais curta sob a mais alta quando dois grupos se unem, o que mantém cada árvore com altura de no máximo log n. A compressão de caminho faz com que cada nó pelo qual find passa aponte diretamente para a raiz, então buscas posteriores a partir desses nós levam uma etapa. Com ambos, qualquer sequência de m operações custa O(m α(n)), o que se comporta como tempo linear.

Qual é a diferença entre Número de Províncias e Número de Ilhas?

Ambos contam componentes conectados. Em Number of Islands, o grafo é uma grade, cada quadrado tem no máximo quatro vizinhos, e o trabalho é O(rows × cols). Aqui, o grafo é fornecido como uma matriz de adjacência: qualquer cidade pode se conectar a qualquer outra, e você lê uma linha inteira com n entradas para listar os vizinhos de uma cidade.

Python

def findCircleNum(isConnected):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]

Esperado