算法
(并查集) $O(k)$
考虑到并查集中并没有断开一条边的操作,同时这里并没有合并操作,所以我们不妨逆序操作:原来的断开一条边也就变成了合并一条边,图上已有的边可忽略。
最后由于答案的更新是从后往前的,所以我们可以用栈来维护。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::stack;
using std::string;
struct UnionFind {
vector<int> par, rank, siz;
UnionFind(int n): par(n, -1), rank(n), siz(n, 1) {}
int root(int x) {
if (par[x] == -1) return x;
else return par[x] = root(par[x]);
}
bool same(int x, int y) {
return root(x) == root(y);
}
bool unite(int x, int y) {
int rx = root(x), ry = root(y);
if (rx == ry) return false;
// union by rank
if (rank[rx] < rank[ry]) std::swap(rx, ry);
par[ry] = rx;
if (rank[rx] == rank[ry]) rank[rx]++;
siz[rx] += siz[ry];
return true;
}
int size(int x) {
return siz[root(x)];
}
};
struct Query {
string type;
int u, v;
};
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
cin >> n >> m >> k;
rep(i, m) {
int u, v;
cin >> u >> v;
}
vector<Query> qs(k);
rep(i, k) {
cin >> qs[i].type >> qs[i].u >> qs[i].v;
--qs[i].u; --qs[i].v;
}
stack<string> st;
UnionFind uf(n);
for (int i = k-1; i >= 0; --i) {
if (qs[i].type == "cut") uf.unite(qs[i].u, qs[i].v);
else {
if (uf.same(qs[i].u, qs[i].v)) st.push("YES");
else st.push("NO");
}
}
while (st.size()) {
cout << st.top() << '\n';
st.pop();
}
return 0;
}