チームXOR

2 secs 1024 MB

解説

この問題はUnionFindを使って効率的に解くことが出来ます。

人 $x$ が所属するチームのxorを $X$ 、人 $y$ が所属するチームのxorを $Y$ とし、この２つのチームが同じでないとします。この時、合併後のxorは $X ^ Y$ となります。 $^$ はxorの演算とします。

この操作をUnionFindでマージする時に行えば良いです。チームのxorはその集合の根ノードに持たせます。