01/02 競プロ典型012

ビンゴのような長方形の表において、指定された二点が繋がっているか判定

初期のグラフはどのマスも有効ではなく、入力に応じて以下の２種類の操作をする

(1)t==1のとき、指定されたマス(x,y)を有効にする

(2)t==2のとき、指定された二点が、有効なマスのみを辿って結ぶことが可能か判定

Union-find木という考え方がいいらしい

根（木の最下層）が同じなら到達可能だよねという考え方

3と4が繋がっているかは、根までそれぞれ辿っていき3→2→1(根)、4→1(根)のように根が同じなら到達可能

UnionFindは四つの操作

init、初期化

配列parをサイズH*W、初期値-1に初期化

この配列は、各マスの根を保存する

root、根の更新と探索

根を更新しながら根を返す

ちょっとよくわからない

unite、根を統合

与えられた二点の根を同じにする

この問題では、(1)で与えられた一点とそれに隣接する四点を統合する

same、根が同じか判定

その通り

(1)の処理をquery1で、(2)の処理をquery2の関数で行っている

むずいけど段々理解

クラスの書き方

class UnionFind{

public:

  func()

};

クラスの変数

UnionFind UF;