0581 - Drumuri
De la Universitas MediaWiki
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
Exemplu 2
- Intrare
0 0 0
- Iesire
Datele de intrare nu corespund restrictiilor impuse
Rezolvare
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()