URI Online Judge | 3131

Índice de Reputação

Por Carlos de Salles, UFMA BR Brazil

Timelimit: 1

Os mecanismos de busca da internet se baseiam em reputação. Quando há um link de uma página para a sua, você ganha reputação em sua página. Mas quanta reputação? Isso depende da quantidade e da qualidade dos links que apontam para sua página. Quanto mais reputação essas outras páginas tiverem, mais reputação você terá.

O PageRank é um dos mais famosos algoritmos de busca da internet e se baseia conceitualmente nesta mesma ideia, com suas especificidades e maior complexidade. A figura a seguir ilustra o algoritmo do PageRank.

UOJ_3131_a.png

Fonte: Wikipedia - PageRank (https://commons.wikimedia.org/wiki/Category:PageRank#/media/File:PageRank-hi-res.png )
 

Sua tarefa é implementar o Algoritmo de Índice de Reputação em um conjunto de páginas, sabendo os links que existem entre tais páginas. Neste problema, as páginas são representadas por inteiros variando de 1 a P (onde P nunca é maior que 100). Também são informados L (um inteiro variando de 1 a 10.000) links entre as P páginas. Um link é uma ligação única de uma página de origem Po para uma página de destino Pd (não pode haver na entrada dois links para o mesmo par Po e Pd). Perceba que não é obrigatório haver um link de volta, no sentido de Pd para Po.

Para calcular o índice de reputação de todas as páginas, primeiro você deve calcular o Grau de Entrada de cada página. O Grau de Entrada de uma página é o número total de links que apontam para aquela página. Dado o Grau de Entrada de todas as páginas, você agora pode calcular o Índice de Reputação de uma página qualquer Pi. O Índice de Reputação da página Pi é igual ao Grau de Entrada daquela página mais o somatório do Grau de Entrada de todas as páginas que possuem um link apontando para a página Pi.

Definido o Algoritmo de Índice de Reputação, você deve escrever um programa que lê a descrição de todos os L links existentes entre P páginas e depois imprime o Índice de Reputação de cada uma das P páginas. Faça isso em ordem crescente, da página 1 até a página P.

Considere o exemplo da figura. Nela há 6 páginas. Os links são representados pelas setas entre a página de origem e a de destino. Os Graus de Entrada (quantidade de links apontando para aquela página) para as páginas de 1 a 6 são, respectivamente, os seguintes: 0; 1; 3; 0; 0; 1. Por sua vez, os Índices de Reputação são esses Graus de Entrada mais o somatório dos Graus de Entrada de todas as páginas vizinhas que apontam para cada página. Dessa forma, os Índices de Reputação das páginas de 1 a 6 são: 0; 1; 4; 0; 0; 4.

UOJ_3131_b.png

Entrada

A entrada inicia por um inteiro P (que pode variar de 1 a 100) em uma linha isolada, representando o número total de páginas daquele caso de teste. Na segunda linha da entrada é informado um inteiro L (que pode variar de 1 a 10.000), informando o número total de links entre as páginas. Seguem L linhas, cada uma delas representando um link, com um par de inteiros O e D (inteiros diferentes e ambos variando de 1 a P), separados por um espaço em branco, informando a página de origem e a página de destino de um link. Não há na entrada um mesmo par O e D de inteiros aparecendo, portanto cada link é único.

Saída

A saída é composta por P linhas. Em cada linha deve ser informado o identificador da página, o caractere : (dois pontos), um espaço em branco e o Índice de Reputação daquela página (um inteiro equivalente ao Grau de Entrada daquela página mais o somatório do Grau de Entrada de todas as páginas que apontam para aquela página). Informe os Índices de Reputação das páginas em ordem crescente, de 1 até P.

Exemplo de Entrada Exemplo de Saída

6
5
1 2
2 3
4 3
5 3
3 6
 

1: 0
2: 1
3: 4
4: 0
5: 0
6: 4
 

4
4
1 2
2 3
3 4
4 1
 

1: 2
2: 2
3: 2
4: 2
 

5
4
1 5
2 5
3 5
4 5
 

1: 0
2: 0
3: 0
4: 0
5: 4