Թոփոլոգիական դասավորում

Ունենք ուղղորդված գրաֆ v գագաթով և e կողով, և ցանկանում ենք դասավորել գագաթները որոշակի կարգով։ Եթե գոյություն ունի կող, որը տանում է v1-ից v2, ապա սկզբնական գագաթը v1 պետք է թվարկման մեջ հայտնվի ավելի շուտ, քան v2։ Այսինքն, դասավորումից հետո, յուրաքանչյուր կող պետք է սկսվի ավելի փոքր ինդեքս ունեցող գագաթից և տանի դեպի ավելի մեծ ինդեքս ունեցող գագաթ։
🤔
Ուշադրություն դարձրեք, որ կարող են լինել տարբեր ճիշտ թոփոլոգիական դասավորություններ: Մյուս կողմից, եթե գրաֆը պարունակում է ցիկլեր, ապա թոփոլոգիական դասավորում գոյություն չունի:
Ալգորիթմը կարելի է իրականացնել Depth-First Search (DFS) մեթոդով, որն սկսվում է յուրաքանչյուր գագաթից, որը դեռևս չի այցելվել։ Յուրաքանչյուր DFS կանչի դեպքում, նախ ռեկուրսիվ կերպով մշակվում են ընթացիկ գագաթի բոլոր «զավակները», և միայն դրանից հետո ընթացիկ գագաթը ներմուծվում է պատասխանների ցանկ։ Այս քայլը կապահովի, որ սկզբնական գագաթը ավելի ուշ կհայտնվի, քան նրանով հասանելի բոլոր գագաթները։ Ալգորիթմի ավարտին ուղղակի շրջում ենք ստացված պատասխանների ցանկը.
used = [False] * n              # օգտագործված գագաթներ
order = []                      # թոփոլոգիական կարգ

def dfs(v):                     # DFS
    used[v] = True              # նշել գագաթը որպես օգտագործված
    for to in g[v]:             # անցնել v գագաթին(next) հարակից յուրաքանչյուր գագաթով
        if not used[to]:        # եթե to-ը դեռ չի օգտագործվել
            dfs(to)             # DFS կանչ to գագաթից
    order.append(v)             # ավելացնել v գագաթը թոփոլոգիական կարգում


for i in range(n):              # անցնել բոլոր գագաթներով
    if not used[i]:             # եթե գագաթը դեռ չի օգտագործվել
        dfs(i)                  # կանչել DFS i գագաթից

print(*order[::-1])             # տպել թոփոլոգիական կարգը

Առաջադրանք: Կազմակերպել դասընթացների ժամանակացույցը

Ձեզ տրված է n դասընթաց, որոնք ցանկանում եք անցնել, և առկա են ընդհանուր առմամբ p նախապայմաններ։ Յուրաքանչյուր նախապայման ներկայացված է որպես զույգ կուրսեր , որը նշանակում է, որ նախ պետք է անցնել դասընթացը, որպեսզի հնարավորություն ունենաք անցնելու դասընթացը (եթե զույգը 1, 2 է, դա նշանակում է, որ պետք է նախ անցնել 2-րդ դասընթացը, ապա 1-ինը):
Պետք է ստուգել, թե արդյոք հնարավոր է ավարտել բոլոր դասընթացները։

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր n և p (1 ≤ n, p ≤ 10 000)։
Հաջորդ p տողերում յուրաքանչյուրն պարունակում է երկու ամբողջ թիվ (1 ≤ ≤ n)։

Ելք

Ծրագիրը ելքում պետք է տպի Yes, եթե հնարավոր է անցնել բոլոր դասընթացները, և No հակառակ դեպքում։

Օրինակներ

Input
Output
2 1 2 1
Yes
2 2 2 1 1 2
No
 

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