首页 > 其他分享 >ATABC293D Tying Rope

ATABC293D Tying Rope

时间:2023-03-12 17:14:48浏览次数:47  
标签:std DSU int 绳子 Rope fa ATABC293D Tying find

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

相关文章