(6 points) Uma rede social de amizades pode ser representada por uma matriz de adjacência de colunas e linhas. Cada linha (ou coluna) contém as relações da pessoa . Considere a matriz de adjacéncia abaixo:
id
0 1 1 0 1
1 0 0 1 0
1 0 0 0 0
0 1 0 0 1
1 0 0 1 0
Esta matriz representa uma rede social entre 5 pessoas: e . Além disso, quando a posição ( ) dá matriz é 1 , então as pessoas e são amigas entre si. Caso a posição ( ) da matriz é 0 , então e não são amigas. Observe que a pessoa é amiga das pessoas e , mas não é amiga da pessoa .
Assim, implemente uma função que recebe uma matriz de adjacência e o número de pessoas contidas nela e que retorna o 1 se há nessa rede social uma pessoa sem amigos e 0 caso contrário. Na matriz exemplo, a sua função deve retornar 0 , pois todas as pessoas tem amigos. Além disso, considere que existe uma definição para o número máximo de pessoas que a matriz comporta, chamado MAX_PESSOAS. O protótipo dessa função deve ser:
int existeIsolados(int M[ ][MAX_PESSOAS], int n);

Passo 1

O enunciado dá uma matriz de adjacência M de dimensão ntimes n que representa amizades entre n pessoas. Cada entrada M[i][j] vale 1 se a pessoa ni é amiga de nj, e 0 caso contrário. Queremos verificar se existe ao menos uma pessoa “isolada” (sem nenhum amigo), ou seja, se em alguma linha i todos os elementos são zero. Se existir, retornamos 1; caso contrário, retornamos 0.

Passo 2

Para cada pessoa i de 0 até n-1, vamos:
  1. Inicializar um acumulador soma = 0.
  2. Percorrer todas as colunas j de 0 até n-1, somando M[i][j] em soma.
  3. Ao fim do laço em j, se soma == 0 significa que a pessoa i não tem amigos, logo retornamos 1 imediatamente.

Passo 3

Se o laço sobre todas as pessoas terminar sem encontrar linha com soma zero, significa que ninguém é isolado, então retornamos 0.

Passo 4

Traduzindo isso em C, considerando que MAX_PESSOAS já está definido previamente, temos:
int existeIsolados(int M[][MAX_PESSOAS], int n) {
    int i, j, soma;
    for (i = 0; i < n; i++) {
        soma = 0;
        for (j = 0; j < n; j++) {
            soma += M[i][j];
        }
        if (soma == 0) {
            return 1;  /* encontrou pessoa isolada */
        }
    }
    return 0;  /* nenhuma pessoa isolada */
}

Resposta

int existeIsolados(int M[][MAX_PESSOAS], int n) {
    int i, j, soma;
    for (i = 0; i < n; i++) {
        soma = 0;
        for (j = 0; j < n; j++) {
            soma += M[i][j];
        }
        if (soma == 0) {
            return 1;
        }
    }
    return 0;
}

Exercícios relacionados