AGrigorii's blog

By AGrigorii, history, 3 years ago, In Russian,

Всем привет! Столкнулся с такой проблемой: а как сжать граф c n ≤ 104, m ≤ 105 (n вершин, m ребер). Т.е. ищем цикл, сжимаем его в одну вершину, и ребра, которые шли в какую-то вершину цикла, перекидываем в нее. Подскажите, пожалуйста, как это сделать оптимально? Как хранить граф, как сливать цикл? Спасибо!

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it