1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

struct PartiallyParsistUnionFind {
  vector<ll> rank, par, time;

  PartiallyParsistUnionFind(ll n) {
    rank.resize(n);
    par.resize(n, -1);
    time.resize(n, LINF);
  }

  ll find(ll t, ll x) {
    if (time[x] > t) return x;
    return find(t, par[x]);
  }

  bool unite(ll t, ll x, ll y) {
    x = find(t, x);
    y = find(t, y);
    if (x == y) return false;
    if (rank[x] > rank[y]) {
      par[y] = x;
      time[y] = t;
    } else {
      par[x] = y;
      time[x] = t;
      if (rank[x] == rank[y]) { rank[y]++; }
    }
    return true;
  }

  bool same(ll t, ll x, ll y) { return find(t, x) == find(t, y); }
};