Number of Provinces

Q: Qual é a complexidade de tempo de Number of Provinces?

O(n²) com uma busca em grafo ou union-find, porque ambos leem cada entrada da matriz n × n uma vez. Union-find adiciona um fator α(n), a função inversa de Ackermann, que na prática é no máximo 4. O espaço extra é O(n).

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 curtos de escrever. Union-find é a melhor ferramenta quando você também precisa responder a muitas perguntas do tipo "essas duas cidades compartilham uma província?", porque cada resposta leva um tempo quase constante.

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 é uma matriz de adjacência: qualquer cidade pode se conectar a qualquer outra, e listar os vizinhos de uma cidade lê uma linha inteira de n entradas.

MédioUnion-find Grafos

+10

Há n cidades, numeradas de 0 a n-1. isConnected[i][j] é 1 quando uma estrada conecta diretamente a cidade i à cidade j, e 0 caso contrário. As estradas funcionam nos dois sentidos, então a matriz é simétrica, e cada cidade está conectada a si mesma.

Uma província é um grupo de cidades em que todas podem alcançar umas às outras, diretamente ou por meio de outras cidades, sem que nenhuma estrada leve para fora 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 onde uma estrada liga duas cidades diretamente
Retornainteger: o número de províncias

Restrições

1 ≤ n ≤ 150, onde 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 liga os dois pares, então há 2 províncias.

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 descreve um grafo não direcionado: as cidades são nós e cada 1 é uma aresta. Uma província é um componente conexo, e um 0 entre duas cidades não as separa quando uma terceira cidade conecta ambas. Uma busca a partir de cada cidade não visitada, ou uma estrutura union-find aplicada a cada aresta, conta os componentes em O(n²).

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

Intuição

Uma cidade não marcada não pode pertencer a uma província que você já contou, porque cada busca marca toda a sua província. Portanto, ela inicia uma nova. A busca percorre as linhas da matriz: no segundo exemplo, a busca a partir da cidade 0 alcança a cidade 1, e a linha da cidade 1 então alcança a cidade 2, embora a linha 0 tenha um 0 para a cidade 2.

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

Algoritmo

Crie uma marcação de visitada para cada cidade e defina a contagem como 0.
Percorra as cidades em ordem e ignore qualquer cidade já visitada.
Em uma cidade não visitada, some 1 à contagem, marque-a e coloque-a em uma pilha.
Enquanto houver cidades na pilha, retire uma e coloque na pilha cada cidade da sua linha que tenha um 1 e ainda não tenha sido visitada, marcando-a 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

Comece com n províncias, uma por cidade. Cada 1 acima da diagonal indica que duas cidades pertencem ao mesmo grupo: se os grupos delas forem diferentes, una-os e diminua a contagem em um. No segundo exemplo, a contagem começa em 5, (0, 1) une as cidades 0 e 1, (1, 2) traz a cidade 2 para o grupo delas, e restam 3 províncias.

Union-find armazena cada grupo como uma árvore: parent[c] aponta um nível acima, e duas cidades pertencem ao mesmo grupo quando find percorre o caminho de ambas até a mesma raiz. Sem otimizações, as uniões podem criar um caminho muito longo, que cada find percorre em O(n) passos. A união por rank coloca a árvore mais baixa sob a mais alta, de modo que nenhum caminho tenha mais do que log n níveis. A compressão de caminho aponta diretamente para a raiz cada cidade por onde find passou. Juntas, essas técnicas tornam cada find amortizado O(α(n)), e α(n) é no máximo 4 na prática.

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 e, em seguida, percorra o caminho novamente, apontando cada cidade nele para a raiz.
Se as raízes forem diferentes, conecte a raiz de menor rank à outra, some 1 ao rank 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

Confiar apenas nas estradas diretas. As cidades 0 e 2 no segundo exemplo têm um 0 entre elas e ainda assim pertencem à mesma província.
Contar os 1s e dividir por dois. Três cidades que estão todas conectadas entre si têm três estradas e uma província.
No union-find, diminuir a contagem para cada 1, em vez de apenas quando as duas raízes são diferentes.
Comparar parent[i] com parent[j]. Duas cidades do mesmo grupo podem ter pais diferentes quando uma delas está em um nível mais profundo; compare find(i) com find(j).
Anexar a própria cidade j, como em parent[j] = find(i). Se j já fazia parte de um grupo, o restante desse grupo fica de fora da união.

Perguntas frequentes3

Qual é a complexidade de tempo de Number of Provinces?

O(n²) com uma busca em grafo ou union-find, porque ambos leem cada entrada da matriz n × n uma vez. Union-find adiciona um fator α(n), a função inversa de Ackermann, que na prática é no máximo 4. O espaço extra é O(n).

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 curtos de escrever. Union-find é a melhor ferramenta quando você também precisa responder a muitas perguntas do tipo "essas duas cidades compartilham uma província?", porque cada resposta leva um tempo quase constante.

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 é uma matriz de adjacência: qualquer cidade pode se conectar a qualquer outra, e listar os vizinhos de uma cidade lê uma linha inteira de n entradas.

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

Teste #1

Teste #2

Argumento

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

Saída Esperada