Solução escrita por Julia Tiosso
O problema apresenta um grafo com $N$ vértices e $M$ arestas. Para cada uma das $Q$ perguntas, você quer adicionar o máximo de arestas possíveis sem que exista um caminho conectando os vértices $A_i$ e $B_i$.
Subtarefa 2: Não existe cidade conectando $B_i$ para todo $1\leq i\leq Q$
Como $B_i$ não está conectado com nenhum outro vértice, podemos considerar todos os demais $N-1$ vértices e adicionar todas as arestas possíveis.
Nesse caso, a quantidade de arestas é simplesmente $\frac{(N-1) \cdot (N-2)}{2}$
Assim, a complexidade é basicamente o tempo de leitura da entrada: $\mathcal{O}(M + Q)$
Subtarefa 3: $N \leq 100$ e o grafo possui duas componentes
Essa subtarefa nos ajuda a pensar em componentes. Aqui, há apenas dois casos para cada pergunta $i$:
- Se $A_i$ e $B_i$ pertencem a mesma componente, então a resposta é $-1$, uma vez que já existe um caminho conectando esses vértices
- Senão, as únicas arestas que não podem existir são aquelas que conectam uma componente à outra:
- Nesse caso, seja $T$ o tamanho da componente de $A_i$, então a quantidade de arestas é $\frac{T \cdot (T – 1)}{2}$, enquanto a da componente de $B_i$ é $\frac{(N-T) \cdot (N-T-1)}{2}$
Como $N \leq 100$, podemos fazer uma DFS para cada pergunta. Iniciamos a DFS no vértice $A_i$, guardando em uma variável o tamanho da componente e usando um vetor de marcação.
Ao terminar, podemos determinar se $B_i$ está na mesma componente de $A_i$ apenas verificando se aquele vértice está marcado ou não. Se sim, a resposta é $-1$. Caso negativo, a quantidade de arestas é a soma explicada acima.
Complexidade: $\mathcal{O}((N + M) \cdot Q)$
Subtarefa 4: O grafo possui duas componentes
Como não há restrição em $N$, devemos processar cada pergunta de maneira mais eficiente. Para isso, vamos fazer uma única DFS no ínicio da solução.
Nessa DFS, além daquilo que já estávamos guardando, vamos também armazenar em qual componente cada vértice está em um vetor.
Assim, para cada pergunta $i$, é possível determinar facilmente as componentes de $A_i$ e $B_i$ e também seus respectivos tamanhos.
Complexidade: $\mathcal{O}(N + M)$
Subtarefa 6: $Q = 1$
Ainda continuamos a pensar nas componentes. Como nas outras subtarefas, sempre é possível adicionar as arestas que conectam vértices de uma mesma componente.
Como queremos maximizar a quantidade de arestas, no final, sempre restará apenas duas componentes, $C_A$ e $C_B$, que contêm $A$ e $B$, respectivamente.
Portanto, o algoritmo consiste em determinar para cada componente do grafo se vamos conectá-la à $C_A$ ou $C_B$. Analisando a quantidade de arestas adicionadas para cada um dos casos, é possível concluir que sempre vale mais a pena conectá-la à componente de maior tamanho.
Dessa forma, a menor componente ficará “isolada” e não poderá haver nenhuma aresta a conectando com as demais. Seja $T$ o menor tamanho entre $C_A$ e $C_B$, então a resposta será $\frac{N \cdot (N-1)}{2}$ $-$ $(N-T) \cdot T$
Complexidade: $\mathcal{O}(N + M)$
Subtarefa 7: Sem restrições adicionais.
Mais uma vez, devemos tentar otimizar o tempo de resposta de uma única pergunta. Para isso, também faremos uma única DFS no ínicio guardando a componente de cada vértice (vetor $\text{comp}$) e o tamanho de cada componente (vetor $\text{tam}$).
Assim, ao receber uma pergunta $A_i, B_i$:
- Verificamos se $\text{comp}[A_i] \text{ == } \text{comp}[B_i] $. Se sim, a resposta é $-1$.
- Se não, então fazemos $T = \min(\text{tam}[\text{comp}[A_i]],\text{tam}[\text{comp}[B_i]])$ e a resposta é $\frac{N \cdot (N-1)}{2}$ $-$ $(N-T) \cdot T$
Em todas as subtarefas, note a importância de usar variáveis do tipo $\text{long long}$, pois o resultado final pode ser maior que o limite do $\text{int}$.
Complexidade: $\mathcal{O}(N + M + Q)$