526互联

并查集优化 - 按大小合并时间复杂度证明

发布时间 2023-07-29 10:43:49作者: huangqixuan

并查集优化 - 按大小合并时间复杂度证明

if(sz[b[x]].size() > sz[b[y]].size()) swap(x, y);
  • 对于每个元素，当它当前所在的集合中，需要有其它大于该集合大小的集合，才会被遍历
  • 如果元素在一个大小 \(1\) 的集合中，会转移到大小 \(2\) 的集合中
  • 如果元素在一个大小 \(2\) 的集合中，会转移到大小 \(4\) 的集合中
  • 如果元素在一个大小 \(4\) 的集合中，会转移到大小 \(8\) 的集合中
  • 如果元素在一个大小 \(8\) 的集合中，会转移到大小 \(16\) 的集合中
  • 因为一开始就进行按秩合并所以每次转移到两倍大小的集合中
  • 所以每个元素转移 \(\log n\) 次
  • 那么总共 \(O(n \log n)\)

并查集暴力 AC

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int MAXN = 4e6 + 3;
const LL mod = 998244353;

int n, m, b[MAXN];
LL ANS = 0;
vector<int> sz[MAXN];

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for(int i = 0; i < n; i++) sz[i].push_back(i), b[i] = i;
  for(int i = 1, opt, x, y; i <= m; i++){
    cin >> opt >> x >> y;
    if(opt == 0){
      if(b[x] == b[y]) continue;
      if(sz[b[x]].size() > sz[b[y]].size()) swap(x, y);
      for(int z : sz[b[x]]){
        sz[b[y]].push_back(z);
        b[z] = b[y];
      }
    }else{
      ANS *= 2, ANS += (b[x] == b[y]);
      ANS %= mod;
    }
  }
  cout << ANS;
  return 0;
}