ATABC293D Tying Rope
题意
有 \(N\) 根一端涂成红色,另一端涂成蓝色的绳子,现进行 \(M\) 次操作,第 \(i\) 次操作给出两个整数 \(A_i\),\(C_i\) 与两个字符 \(B_i\),\(D_i\),表示将第 \(A_i\) 根绳子的 \(B_i\) 端与第 \(C_i\) 根绳子的 \(D_i\) 端连接起来。若字符为 \(\texttt{R}\),则表示红色端,否则为蓝色端。
现在问你 \(M\) 次操作之后绳子形成的环的数量与未能形成环的绳子段数量。
\(N, M \le 2 \times 10^5\)。
思路
看到这种有关连通性的问题,我们首先想到的肯定就是 DSU,也就是并查集。
初始化一个大小为 \(2N\) 的并查集,考虑把第 \(i\) 条绳子拆成 \(i\) 与 \(i + N\) 两个点,分别表示红段与蓝端,并把它们合并,表示他们在一开始就属于同一根绳子。
然后根据每一个操作进行合并,在合并过程中,如果出现了待合并的两个点已经属于同一个绳子段(也就是父亲相同)的情况,则说明出现了环。这样我们就求出了环的数量。
非环的数量也很好做,对每一个点都查询出它的父亲并在桶中打上标记,这样,最后被标记的数量就是总的绳子段的数量,然后再用这个数减去上边所得的环的数量,就是非环的数量。
我个人始终认为只写路径压缩的并查集时间复杂度为 \(\log\) 级别的,因此总体的时间复杂度为 \(O(M \log N)\)。
代码
#include <bits/stdc++.h>
using i64 = long long;
struct DSU {
int n;
std::vector<int> fa;
DSU(int n) {
this->n = n;
fa.resize(n);
std::iota(fa.begin(), fa.end(), 0);
return;
}
int find(int u) {
return u == fa[u] ? u : fa[u] = find(fa[u]);
}
int merge(int u, int v) {
int fau = find(u), fav = find(v);
if (fau == fav) {
return 1;
}
fa[fau] = fav;
return 0;
}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m;
std::cin >> n >> m;
DSU dsu(2 * n + 50);
for (int i = 1; i <= n; i++) {
dsu.merge(i, i + n);
}
int ans = 0;
for (int i = 1; i <= m; i++) {
int u, v;
char a, b;
std::cin >> u >> a >> v >> b;
ans += dsu.merge(u + (a == 'B') * n, v + (b == 'B') * n);
}
std::bitset<(int) 4e5 + 50> b;
for (int i = 1; i <= 2 * n; i++) {
b[dsu.find(i)] = true;
}
std::cout << ans << " " << b.count() - ans << "\n";
return 0;
}
标签:std,DSU,int,绳子,Rope,fa,ATABC293D,Tying,find
From: https://www.cnblogs.com/forgot-dream/p/17208530.html