Union-Findでmerge(a,b)をしたときleaderになるのはaとbでどっちになるか？

結論

mergeを行う前でサイズの大きい方がリーダーになります

疑問に思ったこと

この記事に書かれているa,bはそれぞれの連結成分でのleaderの頂点番号とします。

https://atcoder.jp/contests/abc183/tasks/abc183_f
この問題はマージテクがメインの問題なのですが、一番最新の値を集計しているmapのデータがleaderのところに来るように実装したいです。しかしmerge(a,b)と投げると、a,bでどっちがリーダーになるのかわからないので、どこの頂点にその合成したmapのデータを保存したらいいのか？と疑問に思いました。なので調べてみました。

コードを見てみる

ACLのコードを見てみます。https://github.com/atcoder/ac-library/blob/master/atcoder/dsu.hpp

ACLだと正直読みにくいのでおそらく似た実装をしていると思われるsnukeさんのライブラリ集のdsuを見てみます。https://github.com/atcoder/live_library/blob/master/uf.cpp

コードのコピペです 許可は取ってません許してくれると信じてます()

struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};

mergeするときに何をしているか？を見てみます(ユニオンファインドの仕組みから考えた方が早いような気はしますが一応コードを載せました)。結論としては、「サイズが小さい方から辺を生やしてサイズが大きい方に繋げる」ということをしていて、つまり「サイズの小さい方が大きいやつの子孫になる」という感じです。

なので例えばmerge(a,b)とmerge(b,a)のように、引数の順番を入れ替えてもleaderになる頂点番号が変わることはなく、その連結成分のサイズによってleaderが決まるということでした。

重要なこととして、「leader同士をmergeしたときは、必ずどちらかがleaderとなる」ということがわかります。なのでもしマージテクなどでリーダーに情報を集めたいとなったときは、mergeした後のleaderが、aとbでどちらと同じか？という場合分けをするのが良いのではないかと思います。なおACLそのものユニオンファインドを使わずに、自分でライブラリとしてユニオンファインドをもっておけばmergeのコードを書き換えることでめんどくさい場合分けを防げます。mergeを書き換える系のコードは下のリンク先のコードのようになります。(snukeさんありがとう)
https://atcoder.jp/contests/abc183/submissions/18147402