Simple Graphs
В тази секция ще разгледаме може би най-фундаменталната тема в състезателното програмиране - а именно теория на графите. Ще научим как да представяме графи в паметта по няколко различни начина. Ще разгледаме основните алгоритми за обхождане и търсене в графи: търсене в ширина, търсене в дълбочина, и алгоритъма на Дейкстра. Ще видим какво е минимално покриващо дърво, непресичащи се множества, топологично сортиране. Ще видим и една техника, която помага не само в графови задачи: разширяване на графа.Темите, които биха ви били полезни за тази секция са Графи и представяне на графи, Търсене в дълбочина, Търсене в ширина, и Алгоритъм на Дейкстра,
Откъм задачи това е една от най-дългите секции, като повечето алгоритми са покрити от поне две задачи (а по-основните - дори от повече). В повечето задачи се изисква директна имплементация или съвсем дребна модификация.
Castle
17
|
21
Roads
19
|
25
Speed
29
|
52
Amazing Race
8
|
53
Hidden Words
26
|
22
Chess Adventure
4
|
17
Lovers
37
|
47
White Horses
23
|
42
Cheating
51
|
37
Repairs
35
|
26
Expelliarmus
7
|
13
Maximal Shopping
46
|
31
Shortest Paths
19
|
9
Famous
32
|
22
DJ Krisa T
38
|
24
Snowy Roads
44
|
22
Square
9
|
22
Breakout
11
|
25
End-to-End
3
|
20