UNION FIND FOR CODECHEF QUESTION http://www.codechef.com/ALMA2015/problems/ALMA03/

chota bheem and gcd (https://www.codechef.com/problems/ALMA03 )

1. #include <bits/stdc++.h>
2. using namespace std;
3. 
   
4. #define MAXN 205
5. #define MOD 1000000007
6. int parent[MAXN],A[MAXN];
7. void init()
8. {
9. for(int i=0;i<MAXN;++i)
10. parent[i] = -1;
11. }
13. int find(int i)
14. {
15. if(parent[i]==-1)
16. return i;
17. else
18. return parent[i] = find(parent[i]);
19. }
21. void merge(int x,int y)
22. {
23. x = find(x);
24. y = find(y);
25. if(x!=y)
26. {
27. if(A[x]>A[y])
28. parent[y] = x; /// whose rank is greater will become parent (here Rank work is done by Cost itself)
29. else
30. parent[x] = y;
31. }
32. }
34. int main()
35. {
36. int t,n;
37. scanf("%d",&t);
38. while(t--)
39. {
40. init();
41. scanf("%d",&n);
42. for(int i=0;i<n;++i) 
43. { scanf("%d",A+i); }
45. for(int i=0;i<n;++i)
46. for(int j=i+1;j<n;++j)
47. if(__gcd(A[i],A[j])>1)
48. merge(i,j);


49. long long result = 1;
50. for(int i=0;i<n;++i)
51. if(parent[i]==-1)
52. {
53. result *= A[i];
54. result %= MOD;
55. }
56. printf("%lld\n",result);
57. }
58. }