Médio C++

Interseção de conjuntos

Enunciado

Dados dois std::set<int> lidos da entrada, crie um novo std::set<int> contendo apenas os elementos presentes em ambos. Imprima o resultado em ordem crescente, um por linha. Se não houver interseção, imprima vazio.

Requisitos

  • Ler dois conjuntos de inteiros da entrada padrão (cada conjunto termina com -1).
  • Usar std::set<int> para armazenar os conjuntos e o resultado.
  • Imprimir os elementos da interseção em ordem crescente, um por linha, ou vazio se não houver.

Código inicial

#include <iostream>
#include <set>

int main() {
    std::set<int> a, b, intersecao;
    int x;
    // TODO: ler o primeiro conjunto até -1
    // TODO: ler o segundo conjunto até -1
    // TODO: calcular a interseção e imprimir
    return 0;
}

Saída esperada

2
4
Ver dica

Para cada elemento de a, verifique se está em b usando b.find(x) != b.end() ou b.count(x). Insira no conjunto resultado.

Mostrar solução 
#include <iostream>
#include <set>

int main() {
    std::set<int> a, b, intersecao;
    int x;
    // Lê o primeiro conjunto até -1
    while (std::cin >> x && x != -1) {
        a.insert(x);
    }
    // Lê o segundo conjunto até -1
    while (std::cin >> x && x != -1) {
        b.insert(x);
    }
    // Calcula a interseção
    for (int v : a) {
        if (b.count(v)) {          // se v está em b
            intersecao.insert(v);  // insere no resultado
        }
    }
    // Imprime
    if (intersecao.empty()) {
        std::cout << "vazio\n";
    } else {
        for (int v : intersecao) {
            std::cout << v << "\n";
        }
    }
    return 0;
}

Passo a passo

  1. Declaramos três std::set<int>: a, b e intersecao.
  2. O primeiro laço lê inteiros até encontrar -1 e insere em a (o set ignora duplicatas).
  3. O segundo laço faz o mesmo para b.
  4. Para cada elemento v de a, usamos b.count(v) para verificar se está em b (retorna 0 ou 1).
  5. Se estiver, inserimos v em intersecao.
  6. Verificamos se intersecao está vazia; se sim, imprimimos vazio; caso contrário, iteramos e imprimimos cada elemento.

Por que funciona

std::set mantém os elementos únicos e ordenados. A operação count é O(log n) e retorna quantas vezes o elemento aparece (0 ou 1). Como percorremos a em ordem e inserimos em intersecao, o resultado também fica ordenado. A complexidade é O(n log n).

Erros comuns

  • Ler os conjuntos sem parar no -1: laço infinito ou leitura incorreta.
  • Usar b.find(v) e comparar com b.end() de forma errada: if (b.find(v)) não compila; use if (b.find(v) != b.end()).
  • Esquecer de verificar se a interseção está vazia e imprimir nada em vez de vazio.

Outra forma de resolver

Usar std::set_intersection da biblioteca <algorithm>:

#include <algorithm>
#include <iterator>
std::set<int> intersecao;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                      std::inserter(intersecao, intersecao.begin()));

Essa abordagem é mais declarativa e eficiente (O(n + m)), mas requer que os conjuntos estejam ordenados (o que std::set garante).

Saída esperada

2
4