旅行很有趣-hackerrank解决方案无法理解，请解释吗？

Question

问题：

https://www.hackerrank.com/contests/hack-it-to-win-it-paypal/challenges/q4-traveling-is-fun/problem

1）unionFind实现什么，为什么从j + 1和j = 2 * i用i调用它？

2）getRoot函数实现什么？ ：

   getRoot(itSrc.next(), root) 

干杯！

解决方案：

public static List<Integer> connectedCities(int n, int g, List<Integer> originCities, List<Integer> 
destinationCities) {

    int[] root = new int[n + 1];
    int[] ids = new int[n + 1];

    for (int i = 0; i <= n; i++) {
        root[i] = i;
        ids[i] = 1;
    }

    for (int i = g + 1; i <= n; i++)
        for (int j = 2 * i; j <= n; j += i)
            unionFind(j, i, root, ids);

    List<Integer> res = new ArrayList<>(originCities.size());
    Iterator<Integer> itSrc = originCities.iterator();
    Iterator<Integer> itDest = destinationCities.iterator();

    while (itSrc.hasNext() && itDest.hasNext())
        res.add(getRoot(itSrc.next(), root) == getRoot(itDest.next(), root) ? 1 : 0);

    return res; 
}

---

private static void unionFind(int a, int b, int[] root, int[] ids) {


 int aRoot = getRoot(a, root);
    int bRoot = getRoot(b, root);

    if (aRoot == bRoot)
        return;

    if (ids[aRoot] < ids[bRoot]) {
        root[aRoot] = root[bRoot];
        ids[bRoot] += ids[aRoot];
    } else {
        root[bRoot] = root[aRoot];
        ids[aRoot] += ids[bRoot];
    }

 }

---

 private static int getRoot(int a, int[] root) {
    while (a != root[a])
       a = root[a];
    return a;
 }

---

解决方案链接：https://www.hackerrank.com/contests/hack-it-to-win-it-paypal/challenges/q4-traveling-is-fun/forum/comments/544186

Answer 1

这是关于一种称为不交集的数据结构。您可以通过以下链接进行检查：https://www.geeksforgeeks.org/union-find/