CODE THANKS FESTIVAL 2017 H - Union Sets

問題

N個の頂点がある。頂点には0からN-1まで番号が振られている。初期状態の頂点間には辺が一本もない。ここで、頂点間に辺がM回、追加される。i回目の追加では無向辺e=(x[i],y[i])が追加される。Q個のクエリが与えられる。i個目のクエリでは頂点v[i]とu[i]が同じ連結成分に初めて含まれるのは何回目の辺の追加かを出力する必要がある。M回、辺を追加しても同じ連結成分に含まれることがないときは-１を出力する。

アプローチ

　頂点u[i],v[i]がある辺を追加することによって同一連結成分に含まれたとき、以降の操作によってu[i],v[i]が異なる連結成分に含まれることはない。言い換えれば、u[i],v[i]が同一連結成分内に含まれることがあるならば、次のようなkが存在する。「k番目の辺の追加を境に、u[i]、v[i]は常に同一連結成分に含まれる」。

　u[i],v[i]が同一連結成分に含まれるか否かには追加回数に対する単調性が成立しているから、kは追加回数に対する二分探索によって求められる。同一連結成分判定は部分永続UnionFind木を用いるとO(logN)で計算できるため、二分探索のO(logN)と併せると、kを求めるのはO(log^2(N))で計算できる。空間計算量はO(N)と通常のUnionFind木と変わらない。

　部分永続とは、データ構造について任意の操作後の状態に遡ることができる性質である。部分永続UnionFindの場合、任意の操作直後の状態に遡り、任意の頂点u,vが同一集合に含まれるか否かの判定がO(logN)で行える。

　部分永続UnionFind木の実装法を説明する。UnionFind木の動作には、rootを辿る時の親の付け替えは用いず、データ構造をマージする一般的テクニックのみを用いる。頂点を併合するときに追加する辺に何回目の操作かを記入しておく。辺に記入された番号を頼りに、その辺がある操作の直後に存在していたか否かを判断する。i回目の操作直後における、頂点u,vの同一連結成分判定は、i回目の操作直後におけるroot(u)==root(v)の判定と同値である。頂点xのrootを求めるとき、e=(x,parent(x))が追加されたのがi回目以前ならば、親への辺eを辿ることができる。すなわち、root(x)=root(parent(x))である。一方、e=(x,parent(x))が追加されたのがi回目より後ならば、親への辺eは存在しないとし、現在の頂点xをrootとする。このようにするだけでUnionFind木を部分永続化することができる。

Submission #2096016 - CODE THANKS FESTIVAL 2017(Parallel) | AtCoder