AGrigorii's blog

By AGrigorii, history, 8 years ago, In Russian

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

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