diff options
Diffstat (limited to 'graph/connect.cpp')
| -rw-r--r-- | graph/connect.cpp | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/graph/connect.cpp b/graph/connect.cpp new file mode 100644 index 0000000..28a6f6c --- /dev/null +++ b/graph/connect.cpp @@ -0,0 +1,31 @@ +struct connect { + int n; + vector<pair<int, int>> edges; + LCT lct; // min LCT no updates required + + connect(int n, int m) : n(n), edges(m), lct(n+m) {} + + bool connected(int a, int b) { + return lct.connected(&lct.nodes[a], &lct.nodes[b]); + } + + void addEdge(int a, int b, int id) { + lct.nodes[id + n] = LCT::Node(id + n, id + n); + edges[id] = {a, b}; + if (connected(a, b)) { + int old = lct.query(&lct.nodes[a], &lct.nodes[b]); + if (old < id) eraseEdge(old); + } + if (!connected(a, b)) { + lct.link(&lct.nodes[a], &lct.nodes[id + n]); + lct.link(&lct.nodes[b], &lct.nodes[id + n]); + }} + + void eraseEdge(ll id) { + if (connected(edges[id].first, edges[id].second) && + lct.query(&lct.nodes[edges[id].first], + &lct.nodes[edges[id].second]) == id) { + lct.cut(&lct.nodes[edges[id].first], &lct.nodes[id + n]); + lct.cut(&lct.nodes[edges[id].second], &lct.nodes[id + n]); + }} +};
\ No newline at end of file |