количество подключаемых компонентов

Question

у нас есть n узлы, и соответствующее значение, связанное с каждым узлом, представлено массивом A[].Для любых i и j, где (1<=i,j<=n and i!=j), есть ребро ч / б их, если GCD(A[i],A[j])==1.Мы должны найти число связанных компонентов в графе, образованном ими.

1 ≤ N ≤ 2⋅10^5

1 ≤ A[i] ≤ 2⋅10^5

время равно 0,5 сек.

Я решаю это с помощью непересекающегося множествав O(n^2 log n) время, но оно превышает ограничение по времени.

Я также могу найти главные факторы всех A[i] в O(nlogn) времени. Но не могу использовать его, чтобы найти решение.

Answer 1

Мы можем построить двудольный граф, где левая часть содержит значения массива, а правая часть содержит простые числа в O (nlogn), как вы написали.

Тогда для каждой вершины левой части мы должны найти что (слева)часть) вершины находятся на расстоянии 2 от него (в графе) и соединяются со всеми остальными вершинами (в структуре непересекающихся множеств).

Возможно, наихудший случай второго этапа (при использовании BFS с глубиной 2) является квадратичным, но на практике он может показаться довольно быстрым.