i = 0
do {
j = i + 1;
while ((j < n) && E1) j++;
if (j < n) E2;
} while (j < n);
flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3)
flag = 0;
if (flag)
printf("Sink exists");
else
printf("Sink does not exist");
Elige las expresiones correctas para E3
(A) (A[i][j] && !A[j][i])
(B) (!A[i][j] && A[j][i])
(C) (!A[i ][j] | | A[j][i])
(D) (A[i][j] | | !A[j][i])
Respuesta: (D)
Explicación: La siguiente explicación es para la parte anterior de esta pregunta:
para que el vértice i sea un sumidero, no debe haber ningún borde desde i hacia ningún otro vértice.
De acuerdo con la entrada dada en cuestión,
A[i][j] = 1 means there is an edge from vertex i to j. A[i][j] = 0 means there is no edge from i to j
Para que un Node de i se sumidero,
A[i][j] should be 0 for all j A[j][i] should be 1 for all j.
El pseudocódigo anterior verifica cada vértice i en busca de sumidero, comenzando desde i = 0. Básicamente verifica cada vértice j después de i para ver si es un sumidero. El truco del pseudocódigo es que no busca j más pequeño que i. Es posible que el i seleccionado por este bucle no se sumide. Básicamente se asegura de que no ignoremos un sumidero potencial. La comprobación de si i es realmente un sumidero o no se realiza más tarde después del ciclo do while.
El vértice i es un sumidero potencial mientras que A[i][j] es cero
Por lo tanto, E1 : !A[i][j]
Si la condición anterior es falsa, entonces i no es un sumidero. Todo j < i tampoco puede ser un sumidero porque no hay un borde de i a j.
Ahora, el próximo sumidero potencial puede ser j.
Entonces, E2 : i = j
Explicación de esta pregunta
El siguiente pseudocódigo básicamente verifica si el sumidero potencial seleccionado por el código anterior es realmente un sumidero o no.
flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3)
flag = 0;
la bandera es igual a 0 significa que no es un sumidero. El código establece la bandera 0 tan pronto como descubre que i no es un sumidero.
A node i is not a sink if either of the following two conditions become true for any j not equal to i. A[i][j] is 1 for any j OR A[j][i] is 0 for any j
E3 : (A[i][j] | | !A[j][i])
Por lo tanto, la opción D es correcta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA