永続Union Find

  • 部分永続Union Findとも言うらしい
  • 各uniteしたときに時刻が1進むとして、各時刻での連結情報が取れる、記憶力の良いUF
// cf : https://misteer.hatenablog.com/entry/persistentUF
// 永続UF
struct PersistentUnionFind{
    VI parent; // 親ID
    VI time; // 親が更新された時刻 (更新は1度きり)
    VI rank; // その頂点を根とする木の深さ (根ノードは深さ0)
    ll now; // 時刻(結合回数)
    vector<vector<PII>> num; // (時刻, 頂点数)を要素にもつvector
    
    PersistentUnionFind(ll sz){
      parent.resize(sz);
      rep(i,sz) parent[i]=i;
      now = 0;
      time.resize(sz, inf);
      rank.resize(sz, 0);
      
      num.resize(sz);
      rep(i,sz) num[i].push_back(MP(0,1));
      debug("initialize finished");
    }

    // rankベースの統合
    void unite(ll a, ll b){
      now++;

      ll rootA = findRoot(a, now);
      ll rootB = findRoot(b, now);
      if(rootA==rootB) return;

      // AにBをつけるようにしたい
      if(rank[rootA]<rank[rootB]) swap(rootA, rootB);

      ll merged_size = size(rootA, now) + size(rootB, now);
      num[rootA].push_back(MP(now, merged_size));
      
      // AにBをつなげる (Bの親がA)
      parent[rootB] = rootA;
      time[rootB] = now;
      if(rank[rootA]==rank[rootB]){
        rank[rootA]++;
      }
      debug("unite", a, b, "finished");
    }

    // a : id
    // t : time
    ll findRoot(ll a, ll t){
      // tより後に子になっているならば
      if(time[a]>t){
        return a; // 今はまだaは親
      }
      else{
        // time[a]<=t つまり、tの時点で誰かの子
        // 親がいるので再帰で求める
        return findRoot(parent[a], t);
      }
    }

    // 時刻tにて同じ木に属するか
    bool is_same(ll u, ll v, ll t){
      return findRoot(u,t) == findRoot(v,t);
    }

    // 時刻tにおいて、頂点xを含む木の要素数を返す
    ll size(ll u, ll t){
      ll r = findRoot(u, t);
      // num[r]に(0,1), (10,5), ... というサイズ履歴が入っている
      // (例)
      // t = 3なら?サイズは1
      // t = 10なら?サイズは5
      // t = 15なら?サイズは5
      // 配列のどれかの要素の.secondに、返すべきサイズは入っている
      ll left = 0; // ありうる
      ll right = num[r].size(); // ng
      while(left+1!=right){
        ll center = (left+right)/2;
        if(num[r][center].first>t){
          right = center;
        }else{
          left = center;
        }
      }
      return num[r][left].second;
    }
};

verified