URI (BEECROWD) - 2653 - Dijkstra - Iniciante - C e C++

Buenas! Novamente editando esse post, agora devido à solução na linguagem C! Esse foi um pouco mais complicado em razão de precisar definir uma estrutura, mas a loǵica é basicamente a mesma (só que explícita). Vamos acompanhar para descobrir como se resolve!!!

Plataforma: URI (BEECROWD)

Problema: 2653

Enunciado:

No jogo O Bruxo, Sigismund Dijkstra é o líder do Serviço Secreto Redaniano, por causa disso ele é uma das pessoas mais importantes do mundo.

Além disso Dijkstra possui um grande tesouro, o qual possui diversos tipos de jóias.

Dijkstra está muito curioso para saber quantos tipos de jóias diferentes seu tesouro possui.

Sabendo que você é o melhor programador do continente Dijkstra te contratou para verificar quantos tipos de jóias distintas ele tem em seu tesouro.

Linguagens: C e C++

Solução:

Esse exercício é conceitualmente simples, porém muito chato de resolver usando linguagens que não dispõem do recurso de conjuntos disjuntos já implementado. Dito isso, fica claro porque me deu preguiça de implementar em C, mas eu corrigi isso com o tempo. 😄

Em C++ há disponível a biblioteca set, então a solução fica extremamente simples. Em conjuntos disjuntos não há repetição de elementos, então basta inserir as entradas no conjunto e, quando valores repetidos forem colocados, isso não fará diferença, pois a estrutura ignora essas inserções. Assim, ao concluir as leituras, teremos que utilizar a função size() e assim saberemos o tamanho do conjunto, ou a quantidade de entradas únicas informadas. Simples, não?

Já em C, existem soluções simples, como aquelas em que se aceita o armazenamento de todos os valores e depois se remove os duplicados. No entanto, isso exige diversas consultas ao array, o que torna a solução ineficiente. Uma alternativa é utilizando árvores binárias, em que cada nó possui um dado e um ponteiro para um nó à esquerda e outro para um nó à direita. Assim, dados à esquerda são menores e à direita são maiores. Dessa forma não é necessário fazer muitas comparações para saber onde um dado será inserido na árvore, bem como para saber se o dado já existe. Eu implementei todas as funções da árvore, inclusive a que libera os recursos de memória. No entanto, como após fornecer o resultado o programa é encerrado, nem precisaria dela e acabei omitindo aqui só por uma questão de tornar o código mais simples. Como é uma boa prática liberar memória assim que possível, sugiro que você implemente essa parte no seu código. Como você já sabe, você é livre para alterar este código, propor mudanças e encontrar formas ainda mais eficientes de resolver esse problema.

Veja a minha resposta em C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TAMANHOMAX 1000000

typedef struct No {
    char* dado;
    struct No* esq;
    struct No* dir;
} No;

No* criaNo(char* dado) {
    No* novoNo = (No*)malloc(sizeof(No));
    novoNo->dado = strdup(dado);
    novoNo->esq = novoNo->dir = NULL;
    return novoNo;
}

No* insereNo(No* raiz, char* dado) {
    if (raiz == NULL)
        return criaNo(dado);

    int compare = strcmp(dado, raiz->dado);
    if (compare < 0)
        raiz->esq = insereNo(raiz->esq, dado);
    else if (compare > 0)
        raiz->dir = insereNo(raiz->dir, dado);

    return raiz;
}

void contaDiferentes(No* raiz, int* contador) {
    if (raiz != NULL) {
        contaDiferentes(raiz->esq, contador);
        (*contador)++;
        contaDiferentes(raiz->dir, contador);
    }
}

int main() {
    char str[TAMANHOMAX];
    No* raiz = NULL;
    int contador = 0;

    while (scanf("%s", str) != EOF) {
        raiz = insereNo(raiz, str);
    }

    contaDiferentes(raiz, &contador);
    printf("%i\n", contador);

    return 0;
}

Veja a minha resposta em C++:

#include <iostream>
#include <set>

using namespace std;

int main() {
    
    string str;
    set<string> joia;
    
    while (getline(cin, str))
        joia.insert(str);

    printf("%i\n", joia.size());
    
    return 0;
}