summaryrefslogtreecommitdiff
path: root/graph/connect.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'graph/connect.cpp')
-rw-r--r--graph/connect.cpp31
1 files changed, 0 insertions, 31 deletions
diff --git a/graph/connect.cpp b/graph/connect.cpp
deleted file mode 100644
index 98b5b25..0000000
--- a/graph/connect.cpp
+++ /dev/null
@@ -1,31 +0,0 @@
-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 u, int v) {
- return lct.connected(&lct.nodes[u], &lct.nodes[v]);
- }
-
- void addEdge(int u, int v, int id) {
- lct.nodes[id + n] = LCT::Node(id + n, id + n);
- edges[id] = {u, v};
- if (connected(u, v)) {
- int old = lct.query(&lct.nodes[u], &lct.nodes[v]);
- if (old < id) eraseEdge(old);
- }
- if (!connected(u, v)) {
- lct.link(&lct.nodes[u], &lct.nodes[id + n]);
- lct.link(&lct.nodes[v], &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]);
- }}
-};