網頁

2014年3月4日 星期二

UVa 11987 Almost Union-Find

想法:
  • int Root[] : 表示i這個點存放在哪個Set(也就是Set[Root[i]]裡面可以找到i這個數字)
  • vector<int> Set[] : 每個Set裡面可以存放很多數字
分成三個操作:
  1. Union:如果x和y不在同個Set,那就把元素個數較少的那個Set裡面的每個元素移動到另一個Set,並同時將Root[]重新指向。例如Set[Root[y]]元素較少,就把Set[Root[y]]內的元素加入到Set[Root[x]],並且把Set[Root[y]]的元素n,使得Root[n]=Root[x]。
  2. Move:如果x和y不在同個Set,就把Set[Root[x]]這個Set內的元素x刪除,並在Set[Root[y]]加入x,記得將Root[x] = Root[y]。
  3. Output:輸出Set[Root[x]].size()和該Set內每個元素的和。