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 E 1 y E 2
(A) E1: A[i][j] y E2: i = j;
(B) E1 : !A[i][j] y E2 : i = j + 1;
(C) E1: !A[i][j] y E2 : i = j;
(D) E1: A[i][j] y E2: i = j + 1;
Respuesta: (C)
Explicación: Para que el vértice i sea un sumidero, no debe haber ninguna arista desde i a 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
Por lo tanto, la opción (C) 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