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