Недавно наткнулся на задачу в которой требовалось найти количество пар вершин в ориентированном графе, у которых есть хотя бы один общий предок. Другими словами у вершин (i, j) предок k, если i и j достижимы из k. У кого какие идеи есть?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 163 |
2 | cry | 161 |
3 | maomao90 | 160 |
4 | -is-this-fft- | 159 |
5 | awoo | 158 |
6 | atcoder_official | 157 |
7 | adamant | 155 |
7 | nor | 155 |
9 | maroonrk | 152 |
10 | Dominater069 | 148 |
Недавно наткнулся на задачу в которой требовалось найти количество пар вершин в ориентированном графе, у которых есть хотя бы один общий предок. Другими словами у вершин (i, j) предок k, если i и j достижимы из k. У кого какие идеи есть?
Название |
---|
А можно ссылку на задачу?
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.
Спасибо, отличная идея.