nachinius / linkcuttrees

Link Cut Tree for fast path aggregation calculation on trees and graphs

GitHub

Build Status codecov Coverage Status Join the chat at https://gitter.im/LinkCutTrees/Lobby Latest version

Link Cut Trees

A collection of trees

with operations O(lg n) per operation (amortized)

  • maketree
  • link(v,w)
  • cut(v)
  • findroot(v)
  • pathaggregate(v)