A
UBB · Informatică
257 Raspunsuri multiple

Se consideră algoritmul ceFace() definit alăturat, unde a[][] este un tablou bidimensional care reprezintă matricea de adiacență a unui graf orientat cu n noduri, n≤1000n \le 1000. Dacă a[i][j] = 1, înseamnă că există o muchie de la nodul i la nodul j. v[], comp[] și order[] sunt tablouri unidimensionale, fiecare cu n elemente, inițial toate 0. Metodele d1(i, a, v, n, order, idx) și d2(i, t, comp, n, c) apelate de ceFace() sunt de asemenea definite mai jos.

Algoritm 1

Algorithm ceFace(a, n)
  idx ← 0
  For i ← 1, n execute
    v[i] ← 0
    comp[i] ← 0
  EndFor
  For i ← 1, n execute
    If v[i] = 0 then
      d1(i, a, v, n, order, idx)
    EndIf
  EndFor
  For i ← 1, n execute
    For j ← 1, n execute
      t[i][j] ← a[j][i]
    EndFor
  EndFor
  c ← 0
  For i ← n, 1, −1 execute
    u ← order[i]
    If comp[u] = 0 then
      c ← c + 1
      d2(u, t, comp, n, c)
    EndIf
  EndFor
EndAlgorithm

Algoritm 2

Algorithm d1(i, a, v, n, order, idx)
  v[i] ← 1
  For j ← 1, n execute
    If a[i][j] = 1 AND v[j] = 0 then
      d1(j, a, v, n, order, idx)
    EndIf
  EndFor
  idx ← idx + 1
  order[idx] ← i
EndAlgorithm

Algoritm 3

Algorithm d2(i, t, comp, n, c)
  comp[i] ← c
  For j ← 1, n execute
    If t[i][j] = 1 AND comp[j] = 0 then
      d2(j, t, comp, n, c)
    EndIf
  EndFor
EndAlgorithm

Care dintre următoarele afirmații sunt adevărate?

18 / 32