Descrição do Problema

Uma província está investigando as condições de transporte nas cidades, obtendo uma tabela que lista as estradas existentes e as cidades que conectam diretamente. O objetivo do projeto "Transporte Suave" é garantir que quiasquer duas cudades na província sejam acessíveis por transporte, seja por uma estrada direta ou indiretamente através de outras estradas. O problema consiste em determinar o número mínimo de estradas adicionais que precisam ser construídas para alcançar essa conectividade completa.

Entrada e Saída

A entrada contém múltiplos casos de teste. Cada caso inicia com dois inteiros positivos N (número de cidades, N < 1000) e M (número de estradas), seguidos por M linhas, cada uma com um par de inteiros representando as cidades conectadas por uma estrada. As cidades são numeradas de 1 a N. Note que podem existir múltiplas estradas entre as mesmas cidades. A entrada termina quando N é 0.

Para cada caso de teste, a saída deve ser um único inteiro indicando o número mínimo de estradas adicionais necessárias.

Exemplo de Entrada e Saída

Entrada:
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

Saída:
1
0
2
998

Dica: A entrada pode ser grande, recomanda-se utilizar scanf em C/C++ para eficiência.

Abordagem de Solução com Union-Find

O prbolema pode ser modelado como um grafo não direcionado, onde as cidades são vértices e as estradas são arestas. O objetivo é encontrar o número de componentes conexas no grafo. Se houver k componentes conexas, são necessárias pelo menos k-1 arestas adicionais para conectá-las todas.

O algoritmo Union-Find (ou Conjuntos Disjuntos) é eficiente para isso. Ele mantém conjuntos de vértices conectados e permite unir conjuntos e encontrar o representante (raiz) de um vértice. Ao processar todas as arestas, cada componente conexa é representada por uma raiz única. O número de raízes distintas menos 1 é a resposta.

Implementação em C++

O código a seguir implementa a solução usando Union-Find com compressão de caminho e união por postos (ranks) para otimização. As variáveis e funções foram renomeadas para clareza em português.

#include <cstdio>
#include <vector>
using namespace std;

const int MAX_CIDADES = 1005;
int pai[MAX_CIDADES]; // Array para armazenar o pai de cada cidade
int posto[MAX_CIDADES]; // Array para armazenar o posto (rank) de cada raiz

// Função para encontrar a raiz de uma cidade com compressão de caminho
int encontrar(int cidade) {
    if (pai[cidade] == cidade) return cidade;
    return pai[cidade] = encontrar(pai[cidade]);
}

// Função para unir dois conjuntos representados por suas raízes
void unir(int cidadeA, int cidadeB) {
    int raizA = encontrar(cidadeA);
    int raizB = encontrar(cidadeB);
    if (raizA == raizB) return; // Já estão no mesmo conjunto
    // União por postos para balanceamento
    if (posto[raizA] < posto[raizB]) {
        pai[raizA] = raizB;
    } else if (posto[raizA] > posto[raizB]) {
        pai[raizB] = raizA;
    } else {
        pai[raizB] = raizA;
        posto[raizA]++; // Incrementa o posto quando iguais
    }
}

int main() {
    int numCidades, numEstradas;
    while (scanf("%d %d", &numCidades, &numEstradas) == 2 && numCidades != 0) {
        // Inicialização: cada cidade é sua própria raiz com posto 0
        for (int i = 1; i <= numCidades; i++) {
            pai[i] = i;
            posto[i] = 0;
        }

        // Ler e processar cada estrada
        for (int i = 0; i < numEstradas; i++) {
            int cidadeA, cidadeB;
            scanf("%d %d", &cidadeA, &cidadeB);
            unir(cidadeA, cidadeB);
        }

        // Contar o número de componentes conexas (raízes distintas)
        vector<bool> raizVisitada(numCidades + 1, false);
        int componentes = 0;
        for (int i = 1; i <= numCidades; i++) {
            int raiz = encontrar(i);
            if (!raizVisitada[raiz]) {
                raizVisitada[raiz] = true;
                componentes++;
            }
        }

        // O número mínimo de estradas adicionais é componentes - 1
        printf("%d\n", componentes - 1);
    }
    return 0;
}