1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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 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]);
}}
};
|
