Ալգորիթմներ և Տվյալների Կառուցվածքներ

BFS-ով Կարճագույն Ուղու Երկարությունը

Քանի որ Breadth-First Search (BFS) ալգորիթմը սկսում է մեկ գագաթից և աստիճանաբար անցնում է նրա հարևաններին, կարող ենք պարզել ամենակարճ ուղին սկզբնական գագաթից մինչև գրաֆի մյուս բոլոր գագաթները։ Դրա համար հարկավոր է փոքր-ինչ փոփոխված տարբերակ. ստեղծում ենք d զանգված, որի սկզբնական արժեքները -1 են։ Եթե գագաթի արժեքը մնացել է -1, նշանակում է, որ այն դեռ չի այցելվել։ Իսկ եթե արժեքը դրական է, դա ցույց է տալիս տվյալ գագաթի հեռավորությունը սկզբնական գագաթից:

from collections import deque

n, e = map(int, input().split())        # n: գագաթներ, e: կողեր
g = [[] for _ in range(n)]              # գրաֆ - հարևանության ցուցակ

for _ in range(e):                      # կարդում ենք կողերը
    a, b = map(int, input().split())    # a -> b և b -> a
    g[a].append(b)
    g[b].append(a)

start = int(input())                    # սկիզբ գագաթ
d = [-1] * n                            # հեռավորություն սկզբնական գագաթից
q = deque([start])                      # գագաթների հերթ
d[start] = 0                            # սկզբնական գագաթից ինքն իրեն հեռավորությունը 0 է

while q:                                # մինչև հերթը դատարկ չէ
    v = q.popleft()                     # հերթից ստանում ենք գագաթ
    print(v, end=' ')                   # տպում ենք գագաթը
    for to in g[v]:                     # v-ին կապված յուրաքանչյուր գագաթի համար
        if d[to] == -1:                 # եթե գագաթը դեռ չի այցելվել
            d[to] = d[v] + 1            # (start -> to) = (start -> v) + 1
            q.append(to)                # գագաթը ավելացնում ենք հերթին

print(d)

Սկզբում d զանգվածը սահմանված է -1-երով, ինչը ցույց է տալիս, որ ոչ մի գագաթ դեռ չի օգտագործվել։ Այնուհետև d[start]-ը դրվում է 0, որպեսզի ցույց տանք, որ սկզբնական գագաթից մինչև ինքն իրեն հեռավորությունը 0 է։

Ալգորիթմի կատարման ընթացքում, երբ ավելի շատ գագաթներ են մշակվում, դրանց հեռավորությունները համապատասխանաբար լրացվում են d զանգվածում։ Այդպես մենք ստանում ենք սկիզբ գագաթից մինչև բոլոր մյուս գագաթների հեռավորությունները։

Եկեք տեսնենք ալգորիթմի քայլերը մի քանի օրինակների վրա:

n = 4, e = 4

The input a, b pairs are the following: [(0, 1), (0, 2), (1, 2), (3, 2)]

The starting vertex is 3

  1. d = [-1, -1, -1, 0], q = [3]

  2. v = 3, q = [] → add all the neighbors that are not used to the queue

  3. d = [-1, -1, 1, 0], q = [2]

  4. v = 2, q = [] → add all the neighbors that are not used to the queue

  5. d = [2, 2, 1, 0], q = [0, 1]

  6. v = 0, q = [1] → add all the neighbors that are not used to the queue

  7. v = 1, q = [] → add all the neighbors that are not used to the queue

  8. Done

n = 5, e = 4

The input a, b pairs are the following: [(0, 1), (0, 2), (1, 2), (3, 4)]

The starting vertex is 0

  1. d = [0, -1, -1, -1, -1], q = [0]

  2. v = 0, q = [] → add all the neighbors that are not used to the queue

  3. d = [0, 1, 1, -1, -1], q = [1, 2]

  4. v = 1, q = [2] → add all the neighbors that are not used to the queue

  5. v = 2, q = [] → add all the neighbors that are not used to the queue

  6. Done

    Notice how nodes 3 and 4 were never visited.

    They were not connected to the initial node 0.

Առաջադրանք: Գտնել Կարճագույն Ուղու Երկարությունը

Տրված է անուղղորդ գրաֆ, որտեղ v գագաթների քանակն է, իսկ e-ն կողերի քանակը։ Պահանջվում է հաշվարկել ամենակարճ ուղու երկարությունը գագաթ 1-ից մինչև գագաթ v։ Եթե դրանք կապակցված չեն, ծրագիրը պետք է տպի Impossible։

Մուտք

Մուտքի առաջին տողում տրվում են երկու ամբողջ թիվ v (1 ≤ v ≤ 100 000) և e (1 ≤ e ≤ 100 000)։

Շարունակվող e տողերում տրվում են զույգ ամբողջ թվեր v1, v2 (1 ≤ v1, v2 ≤ v), որոնք ցույց են տալիս, որ գագաթ v1-ը կապված է գագաթ v2-ի հետ և հակառակը։

Ելք

Ծրագիրը պետք է տպի 1-ից մինչև v գագաթի ամենակարճ ուղու երկարությունը։

Օրինակներ

Մուտք

Ելք

5 6 1 2 2 3 1 3 3 4 4 3 3 5

2

2 1 1 2

1

2 0

Impossible

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue