Ունենք ուղղորդված գրաֆ 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 հակառակ դեպքում։