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

Revision ru2, by Loud_Scream, 2016-01-03 00:16:57

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

Tags dfs, bfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian Loud_Scream 2016-01-03 00:16:57 1 Мелкая правка: ' один общи предок. Д' -> ' один общий предок. Д'
ru1 Russian Loud_Scream 2016-01-02 23:47:01 313 Первая редакция (опубликовано)