Codrut Borcutean: Pagină nouă: == Cerinţa == Se dă un graf orientat cu '''n''' noduri și un nod '''p'''. Să se afișeze toate nodurile '''q''' ale grafului, diferite de '''p''', cu proprietatea că există cel puțin un drum de la '''p''' la '''q''' și lungimea drumului minim este pară. == Date de intrare == Programul citește de la tastatură numărul '''n''' de noduri, nodul '''p''' și numărul '''m''' de arce, iar apoi lista arcelor, formată din '''m''' perechi de forma '''i j''', cu semnificaț...

2024-01-04T15:17:04Z

Pagină nouă: == Cerinţa == Se dă un graf orientat cu '''n''' noduri și un nod '''p'''. Să se afișeze toate nodurile '''q''' ale grafului, diferite de '''p''', cu proprietatea că există cel puțin un drum de la '''p''' la '''q''' și lungimea drumului minim este pară. == Date de intrare == Programul citește de la tastatură numărul '''n''' de noduri, nodul '''p''' și numărul '''m''' de arce, iar apoi lista arcelor, formată din '''m''' perechi de forma '''i j''', cu semnificaț...

New page

== Cerinţa ==
Se dă un graf orientat cu '''n''' noduri și un nod '''p'''. Să se afișeze toate nodurile '''q''' ale grafului, diferite de '''p''', cu proprietatea că există cel puțin un drum de la '''p''' la '''q''' și lungimea drumului minim este pară.
== Date de intrare ==
Programul citește de la tastatură numărul '''n''' de noduri, nodul '''p''' și numărul '''m''' de arce, iar apoi lista arcelor, formată din '''m''' perechi de forma '''i j''', cu semnificația că există arc orientat de la nodul '''i''' la nodul '''j'''.
== Date de ieșire ==
Programul va afișa pe ecran numărul '''C''' de noduri care respectă cerința, iar pe rândul următor cele '''C''' noduri, în ordine crescătoare, separate prin exact un spațiu.
== Restricţii şi precizări ==
* '''1 ≤ n ≤ 100'''
* prin drum minim se înțelege drum de cu lungimea minimă
== Exemplu 1 ==
; Intrare
7 2 10
1 2
2 3
2 5
3 4
3 6
4 7
5 1
5 3
5 4
6 5
; Iesire
Datele de intrare corespund restrictiilor impuse
3
1 4 6
<br>
== Exemplu 2 ==
; Intrare
0 0 0
; Iesire
Datele de intrare nu corespund restrictiilor impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
def verifica_restrictii(n, arce):
# Verifică dacă datele de intrare respectă restricțiile
if not (1 <= n <= 100) or not all(1 <= i <= n and 1 <= j <= n for i, j in arce):
return False
return True

def noduri_drum_par(n, p, arce):
# Crează un dicționar pentru a stoca vecinii fiecărui nod
vecini = {i: [] for i in range(1, n + 1)}
for i, j in arce:
vecini[i].append(j)

# Inițializează distanțele de la nodul p la toate celelalte noduri
dist = [float('inf')] * (n + 1)
dist[p] = 0

# Aplică algoritmul lui Dijkstra pentru a calcula distanțele minime
vizitat = [False] * (n + 1)
for _ in range(n):
u = min((d, i) for i, d in enumerate(dist) if not vizitat[i])[1]
vizitat[u] = True
for v in vecini[u]:
if dist[u] + 1 < dist[v]:
dist[v] = dist[u] + 1

# Determină nodurile care au un drum de lungime pară de la nodul p
noduri = [i for i in range(1, n + 1) if i != p and dist[i] % 2 == 0]

return noduri

def main():
n, p, m = map(int, input().split())
arce = [tuple(map(int, input().split())) for _ in range(m)]

# Verifică dacă datele de intrare respectă restricțiile
if not verifica_restrictii(n, arce):
print("Datele de intrare nu corespund restrictiilor impuse")
return

print("Datele de intrare corespund restrictiilor impuse")

# Determină nodurile care au un drum de lungime pară de la nodul p
noduri = noduri_drum_par(n, p, arce)

# Afiseaza rezultatul
print(len(noduri))
print(' '.join(map(str, sorted(noduri))))

if __name__ == "__main__":
main()

</syntaxhighlight>

0581 - Drumuri - Revision history