Given an array $A$ having $N$ elements. Consider an undirected graph $G$ with $N$ vertices. There is an edge between two vertices $i$ and $j$ if and only if $A_i$ and $A_j$ are coprime. I am required to find number of connected components in graph $G$.
I tried a brute force approach to solve this problem. For each pair of elements in $A$, if their GCD is $1$, then I add an edge between them and finally use Depth First Search to find number of components. But this approach is $O(n^{2}\log(n))$. Is there any way I can do it in better say, $O(n\log(n))$ ?
I do not believe it's possible to achieve $O(n*log(n))$. Suppose all the numbers in a given set are co-prime. You will have to check all pairs to make sure they are co-prime. Although I can't prove it.
But you can get better than $O(n^2 * log(n))$.
Check out Disjoined set data structure
Using this approach you can get the connected components at $O(\alpha(n^2))$, where $\alpha$ is an inverse Ackermann function. It grows slightly faster than linear, but the difference is ridiculously small.
The algorithm uses couple of clever tricks, but looks approximately like this.
Each node in the graph remembers it's "parent", the parent and the node belong to the same connected component. In the beginning each node's parent is the node itself and we have $n$ components. Than we add edges one by one and update this "child-parent" structure. In the end each node's parent would be a representative of the component. So that two nodes belong to the same component iff their parents are the same.
After that you only need to sort the array by the value of parent ($O(n*log(n))$) and calculate the number of different parents ($O(n)$). So the total complexity is $O(\alpha(n^2))$.