818. Aeroporto

Olá meus amigos nerds, depois de algumas decepções na última semana, nada melhor que afogar as mágoas resolvendo alguns problemas! E hoje eu trago um problema simples para vocês.

A crescente utilização do transporte aéreo preocupa os especialistas, que prevêem que o congestionamento em aeroportos poderá se tornar um grande problema no futuro. Pensando nisso, o problema 818. Aeroporto nos pede para determinar, a partir de uma listagem de aeroportos e vôos, qual aeroporto possui maior probabilidade de congestionamento no futuro. Como medida da probabilidade de congestionamento o problema usa a soma do número de vôos que chegam e que partem de cada aeroporto. Mais especificamente, o problema pede o identificador do aeroporto que possui maior tráfego aéreo, onde o tráfego é medido pela soma do número de vôos que chegam e que partem do aeroporto.

Modelagem

A simples leitura do problema sugere uma modelagem por grafos. Podemos representar cada aeroporto por um vértice no nosso grafo, assim cada aresta representará um vôo de um aeroporto para outro. Nessa modelagem, o tráfego de cada aeroporto corresponde ao grau do vértice que representa aquele aeroporto. Assim, a resposta para nosso problema é o maior grau dos vértices de nosso grafo.

Computar o grau de cada vértice é bastante simples:

para cada aresta (v1->v2) do grafo

    grau_saída[v1]++

    grau_entrada[v2]++

Observe que o algoritmo acima funciona mesmo que o grafo tenha arestas paralelas (o que pode ser o caso em nosso problema).

Logo o tráfego em cada aeroporto A será:

trafego[A] = grau_saída[A] + grau_entrada[A]

Assim a resposta do problema será o maior elemento do vetor trafego.

Implementação