Нахождение количества пар вершин, у которых есть хотя бы один общий предок.

Правка ru1, от Loud_Scream, 2016-01-02 23:47:01

Недавно наткнулся на задачу в которой требовалось найти количество пар вершин в ориентированном графе, у которых есть хотя бы один общи предок. Другими словами у вершин (i, j) предок k, если i и j достижимы из k. У кого какие идеи есть?

Теги dfs, bfs

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский Loud_Scream 2016-01-03 00:16:57 1 Мелкая правка: ' один общи предок. Д' -> ' один общий предок. Д'
ru1 Русский Loud_Scream 2016-01-02 23:47:01 313 Первая редакция (опубликовано)