Недавно наткнулся на задачу в которой требовалось найти количество пар вершин в ориентированном графе, у которых есть хотя бы один общий предок. Другими словами у вершин (i, j) предок k, если i и j достижимы из k. У кого какие идеи есть?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 160 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | Dominater069 | 154 |
| 8 | awoo | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 12:50:14 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
А можно ссылку на задачу?
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.
Спасибо, отличная идея.