UVa - 13153 ( Number Of Connected Components ) [ Analysis + Solution ]

=>Try Yourself First. For help Scroll Down .

Problem Link:  https://uva.onlinejudge.org/external/131/13153.pdf

⇒ Problem Clearance: 

You will be given N numbers which is between 1 & 10⁶ . And you can draw an edge between any two number if the Greatest Common Divisor ( GCD ) of those two number is greater than 1 . Hence you made some conntection ( probably none ) among the nodes. Now you're going to find number of component that are connected together. 

⇒ Required Knowledge: 

Sieve of Erathothense + Prime Factorization + Depth First Search / Disjoint Set Union .

😤 Wow!!! Got the idea how to solve ??? Then Code it.😤

😡 Not Yet !! Continue Reading . 😡

⇒ How To Solve ??: 

1) Generate primes upto 106 . 

2) Then for each of the Aith number find out the Prime Factorization. And connect those prime with that number.
How to connect ??? 
Well, I solved the problem using the Disjoint Set Union algorithm. Suppose I got the primes P1, P2, P3, P4, .....  Now for each of them I put them into the same union with same Parent for each of the number. If you don't get the previous line then you must read about DSU first. 

That's how we connect the Primes with a specific number.
3) Almost 75% of the work has done. In this step, you just have to count how many different parent you got till now . You can do this by checking each parent of Aith .
Voila !!! Solved !!! 











⇒ Wrong Answer ????

Just think a bit. Is there any implementation error you did? Try to give an input of N prime number and see whether the result is N or not ? I mean check the result of following case is 4 or Not ? 
4
2 3 5 7
Try several cases like this . If they are giving correct output then there may be some corner case you missed. Try to open the next spoiler hint for you.

⇒ Spoiler :

Watch carefully. The number would be in between 1 - 10⁶ . So let if the data set contain multiple 1. Then the total number of 1s will be added to the result.
Why ?? Beacuse if you can not connect a number with 1 as the GCD of 1 and any other number is 1. 

If you did not any implementation mistake in your code then your should be solved by now. If you're failed to solve yet then you may see the Solution given below or you may read the whole post once again and then code it again.

⇒ Code:

=>Leave a comment for any kinds of Hugs and / or Bugs. Thank you .