https://wiki.universitas.ro/index.php?action=history&feed=atom&title=0582_-_Turneu0582 - Turneu - Revision history2026-05-01T09:55:05ZRevision history for this page on the wikiMediaWiki 1.42.1https://wiki.universitas.ro/index.php?title=0582_-_Turneu&diff=8977&oldid=prevCodrut Borcutean: Pagină nouă: Un '''graf orientat''' se numește graf turneu dacă oricare ar fi două noduri diferite '''i, j''', între ele există un singur arc: arcul '''(i j)''' sau arcul '''(j i)'''. În orice graf turneu există un drum elementar care trece prin toate nodurile grafului. == Cerinţa == Se dă un graf turneu cu '''n''' noduri. Să se determine un drum elementar care să conțină toate nodurile grafului. == Date de intrare == Programul citește de la tastatură numărul de noduri '''...2024-01-04T15:08:36Z<p>Pagină nouă: Un '''graf orientat''' se numește graf turneu dacă oricare ar fi două noduri diferite '''i, j''', între ele există un singur arc: arcul '''(i j)''' sau arcul '''(j i)'''. În orice graf turneu există un drum elementar care trece prin toate nodurile grafului. == Cerinţa == Se dă un graf turneu cu '''n''' noduri. Să se determine un drum elementar care să conțină toate nodurile grafului. == Date de intrare == Programul citește de la tastatură numărul de noduri '''...</p>
<p><b>New page</b></p><div>Un '''graf orientat''' se numește graf turneu dacă oricare ar fi două noduri diferite '''i, j''', între ele există un singur arc: arcul '''(i j)''' sau arcul '''(j i)'''. În orice graf turneu există un drum elementar care trece prin toate nodurile grafului.<br />
== Cerinţa ==<br />
Se dă un graf turneu cu '''n''' noduri. Să se determine un drum elementar care să conțină toate nodurile grafului.<br />
== Date de intrare ==<br />
Programul citește de la tastatură numărul de noduri '''n''', iar apoi '''n*(n-1)/2''' perechi '''i j''', cu semnificația că există arcul '''(i j)'''.<br />
== Date de ieșire ==<br />
Programul va afișa pe ecran cele '''n''' noduri ale drumului determinat, separate prin exact un spațiu.<br />
== Restricţii şi precizări ==<br />
* '''1 ≤ n ≤ 100'''<br />
* orice drum corect determinat este acceptat<br />
== Exemplu 1 ==<br />
; Intrare<br />
4<br />
1 4<br />
2 1<br />
2 4<br />
3 1<br />
3 2<br />
4 3<br />
; Iesire<br />
Datele de intrare corespund restrictiilor impuse<br />
1 4 3 2<br />
<br><br />
== Exemplu 2 ==<br />
; Intrare<br />
0<br />
; Iesire<br />
Datele de intrare nu corespund restrictiilor impuse<br />
<br><br />
== Rezolvare ==<br />
<syntaxhighlight lang="python" line><br />
def verifica_restrictii(n, arce):<br />
# Verifică dacă datele de intrare respectă restricțiile<br />
if not (1 <= n <= 100) or not all(1 <= i <= n and 1 <= j <= n for i, j in arce):<br />
return False<br />
return True<br />
<br />
<br />
def drum_elementar(n, arce):<br />
# Crează un dicționar pentru a stoca vecinii fiecărui nod<br />
vecini = {i: [] for i in range(1, n + 1)}<br />
for i, j in arce:<br />
vecini[i].append(j)<br />
<br />
# Alege un nod de start arbitrar<br />
nod_curent = 1<br />
<br />
# Inițializează drumul cu nodul de start<br />
drum = [nod_curent]<br />
<br />
# Construiește drumul<br />
while len(drum) < n:<br />
for nod in sorted(vecini[nod_curent]):<br />
if nod not in drum:<br />
drum.append(nod)<br />
nod_curent = nod<br />
break<br />
<br />
return drum<br />
<br />
<br />
def main():<br />
n = int(input())<br />
arce = [tuple(map(int, input().split())) for _ in range(n * (n - 1) // 2)]<br />
<br />
# Verifică dacă datele de intrare respectă restricțiile<br />
if not verifica_restrictii(n, arce):<br />
print("Datele de intrare nu corespund restrictiilor impuse")<br />
return<br />
<br />
print("Datele de intrare corespund restrictiilor impuse")<br />
<br />
# Determină un drum elementar care să conțină toate nodurile grafului<br />
drum = drum_elementar(n, arce)<br />
<br />
# Afiseaza rezultatul<br />
print(' '.join(map(str, drum)))<br />
<br />
<br />
if __name__ == "__main__":<br />
main()<br />
<br />
<br />
</syntaxhighlight></div>Codrut Borcutean