(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);
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 |
Assim, implemente uma função que recebe uma matriz de adjacência
int existeIsolados(int M[ ][MAX_PESSOAS], int n);
Passo 1
O enunciado dá uma matriz de adjacência
de dimensão
que representa amizades entre
pessoas. Cada entrada
vale 1 se a pessoa
é amiga de
, e 0 caso contrário. Queremos verificar se existe ao menos uma pessoa “isolada” (sem nenhum amigo), ou seja, se em alguma linha
todos os elementos são zero. Se existir, retornamos 1; caso contrário, retornamos 0.
Passo 2
Para cada pessoa
de
até
, vamos:
- Inicializar um acumulador
soma = 0
. - Percorrer todas as colunas
de até , somando M[i][j]
emsoma
. - Ao fim do laço em
, se soma == 0
significa que a pessoanã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;
}