Недавно наткнулся на задачу в которой требовалось найти количество пар вершин в ориентированном графе, у которых есть хотя бы один общий предок. Другими словами у вершин (i, j) предок k, если i и j достижимы из k. У кого какие идеи есть?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3976 |
| 2 | tourist | 3815 |
| 3 | jqdai0815 | 3682 |
| 4 | ksun48 | 3614 |
| 5 | orzdevinwang | 3526 |
| 6 | ecnerwala | 3514 |
| 7 | Benq | 3482 |
| 8 | hos.lyric | 3382 |
| 9 | gamegame | 3374 |
| 10 | heuristica | 3357 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | -is-this-fft- | 165 |
| 3 | Um_nik | 161 |
| 3 | atcoder_official | 161 |
| 5 | djm03178 | 157 |
| 6 | Dominater069 | 156 |
| 7 | adamant | 154 |
| 8 | luogu_official | 152 |
| 9 | awoo | 151 |
| 10 | TheScrasse | 147 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2025 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.01.2025 11:16:03 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
А можно ссылку на задачу?
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.
Спасибо, отличная идея.