Недавно наткнулся на задачу в которой требовалось найти количество пар вершин в ориентированном графе, у которых есть хотя бы один общий предок. Другими словами у вершин (i, j) предок k, если i и j достижимы из k. У кого какие идеи есть?
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3390 |
| 6 | Um_nik | 3387 |
| 7 | tourist | 3384 |
| 8 | heuristica | 3322 |
| 9 | turmax | 3319 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | AmShZ | 142 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | maroonrk | 134 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 06.10.2026 06:46:51 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
А можно ссылку на задачу?
http://www.e-olymp.com/ru/problems/3298
Мне кажется, что ограничения и TL намекают на решение за VE. Сожмем компоненты сильной связности и дальше решим задачу для ациклического графа. Насчитаем динамику dp[a][b] — правда ли что (a,b) — хорошая пара. 1) Если из a достижима b или наоборот, то пара хорошая (эти пары можно найти, запустив dfs из каждой вершины) 2) Иначе пара хорошая, только если есть вершина p, такая что dp[a][p]=true и есть ребро (p->b). Суммарно таких переходов Е
А после, получая ответ, нужно для каждой сильной компоненты связности умножить на ее размер?
А почему критерием является именно существование ребра между b и p, а не равенство dp[b][p] = true?
Ну пусть такая вершина есть, и она не а и не b. Посторем пути из k в а и из k в b. Очевидно, что последнее ребро на пути из k в b входит в b.
А, не, фигню написал.
Это задача с опенкапа гран-при Украины Associated Vertices.
Нужно сделать два графа — первый с исходным набором ребер, второй — с обратным.
Затем из каждой вершины нужно запустить бфс по состояниям. Состояние (ver, last) будет говорить, а правда ли что можно прийти в вершину ver, где last — граф, по которому мы ходили. Если мы ходили по обычному, то если есть ребра в обратном — можно по ним ходить. Если последний раз мы ходили по обратным ребрам — то только по ним и ходим.
Code here.
Спасибо, отличная идея.