0581 - Drumuri

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()