My ICT teacher asked me to give a short lecture at school on a programming topic I'm interested in. I chose finding strongly connected components in a directed graph. I'd like to include a problem to have some context.
Can you recommend simple SCC problems with no other algorithm needed I can use for the lecture?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Kevin114514 | 3655 |
| 3 | Benq | 3650 |
| 4 | maroonrk | 3427 |
| 5 | strapple | 3413 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | tourist | 3301 |
| 9 | turmax | 3297 |
| 10 | squareOf105 | 3262 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | maspy | 150 |
| 3 | nik_exists | 149 |
| 4 | Um_nik | 145 |
| 5 | Errichto | 139 |
| 6 | adamant | 136 |
| 7 | maroonrk | 134 |
| 8 | AmShZ | 133 |
| 8 | BledDest | 133 |
| 10 | DNR | 130 |
CSES- Flight Routes Check
https://cses.fi/problemset/task/1682
CSES- Planets and Kingdoms
https://cses.fi/problemset/task/1683
CSES- Coin Collector
https://cses.fi/problemset/task/1686
The first one does not require knowledge of Strongly Connected Components but it can be solved using the concept. The second one is probably the most instructive. The third one requires applying DP to the constructed components, you can take it up if you have time
Thank you so much.
what is ICT?