Почему мой алгоритм поиска несвязанных множеств Union для этой задачи не проходит все тестовые случаи?

Question

Пример ввода:

1
3 2
1 2
2 3

Первая строка = количество тестов

Первая цифра второй строки = количество человек

Вторая цифра второй строки = числодружбы, F

После F строк = дружба

Выводом будет размер самой большой группы друзей.

Итак, пример вывода для этого входа будет 3. ([1, 2, 3])

Мое решение:

import java.util.Scanner;
import java.util.HashMap;
import java.util.Collections;

public class Main {

    public static void main (String args[]) {
        Scanner reader = new Scanner(System.in);
        int tests = reader.nextInt();
        for (int i = 0; i < tests; i++) {
            int numcitizens = reader.nextInt();
            // the input is 1-indexed so I create the parent array as such
            int[] parent = new int[numcitizens + 1];
            for (int j = 0; j < (numcitizens + 1); j++) {
                parent[j] = j;
            }
            int[] rank = new int[numcitizens + 1];
            int numpairs = reader.nextInt();
            for (int j = 0; j < numpairs; j++) {
                int A = reader.nextInt();
                int B = reader.nextInt();
                union(A, B, parent, rank);
            }
            HashMap<Integer, Integer> histo = new HashMap<Integer, Integer>();
            for (int j = 1; j < parent.length; j++) {
                int root = parent[j];
                if (!histo.containsKey(root)) {
                    histo.put(root, 1);
                }
                else {
                    histo.put(root, histo.get(root) + 1);
                }

            }
            int max = Collections.max(histo.values());
            System.out.println(max);
        }
    }

    // UFDS find
    static int find(int x, int[] parent) {

        if (parent[x]!= x) {
            parent[x] = find(parent[x], parent);
        }

        return parent[x];
    }

    // UFDS union
    static void union(int x, int y, int[] parent, int[] rank) {
        int xRoot = find(x, parent);
        int yRoot = find(y, parent);

        if (xRoot == yRoot) {
            return;
        }
        else {
            if (rank[xRoot] < rank[yRoot]) {
                parent[xRoot] = yRoot;
            }

            else if (rank[yRoot] < rank[xRoot]) {
                parent[yRoot] = xRoot;
            }

            else {
                parent[yRoot] = xRoot;
                for (int i = 0; i < parent.length; i++) {
                    if (parent[i] == yRoot) {
                        parent[i] = xRoot;
                    }
                }
                rank[xRoot] = rank[xRoot] + 1;
            }
        }
    }
}

Это работает для ввода ввода, но при прохождении через систему онлайн-судьи, которая проходит через сотни тестовых случаев, он сообщает мне неверный вывод.Не знаете, где может быть моя ошибка?Для меня это простая проблема UFDS.

Answer 1

Цикл for, который вы вставили union, ухудшает производительность. Просто возьми это.

В цикле гистограммы вам нужно int root = find(j,parent);

Ваш код вызывает исключение, когда numcitizens равен нулю.

Исправьте это, и ваш код будет работать, я думаю.

Вот пара дополнительных советов:

• Я всегда объединяюсь по размеру, а не по рангу. Он имеет такую ​​же сложность, а размер часто бывает полезен. В этом случае вам не нужно будет строить гистограмму, потому что у вас будет размер каждого корня.

• Я использую один массив int[] для структуры данных. Если значение v равно> = 0, то это корневой набор с таким размером (0 означает, что по этому индексу нет набора или пустого набора). В противном случае ~ v является ссылкой на родительский набор. Недавно я использовал эту структуру в этом ответе: Алгоритм: используйте объединение найти для подсчета числа островов

Answer 2

Количество друзей, которое имеет каждый человек, не является массивом parent. Ранком каждого человека является высота дерева, представленная набором, то есть количеством друзей, которых имеет этот человек.поэтому используйте root=rank[j]+1 в цикле for для подсчета макс. друзей.

int max=Integer.MAX_VALUE;
for(int r:rank){
    max=Math.max(max,r+1);
}
System.out.println(max);