Maruf_Hasan

Equalizing money..DSU

Mar 29th, 2019
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.76 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int arr[2000];
  4. int si[2000];
  5. int total[2000];
  6. void initialize(int N)
  7. {
  8. for(int i=0;i<=N;i++)
  9. {
  10. arr[i]=i;
  11. si[i]=1;
  12. }
  13. return;
  14. }
  15. int root(int i)
  16. {
  17. while(i!=arr[i])
  18. {
  19. i=arr[i];
  20. }
  21. return i;
  22. }
  23. void weighted_union(int A,int B)
  24. {
  25. int root_A=root(A);
  26. int root_B=root(B);
  27. if(si[root_A]<si[root_B])
  28. {
  29. arr[root_A]=arr[root_B];
  30. si[root_B]+=si[root_A];
  31. total[root_B]+=total[root_A];
  32. return;
  33.  
  34. }
  35. else
  36. {
  37. arr[root_B]=arr[root_A];
  38. si[root_A]+=si[root_B];
  39. total[root_A]+=total[root_B];
  40. return;
  41. }
  42. }
  43. int main()
  44. {
  45. int t,kase=1;
  46. scanf("%d",&t);
  47. while(t>=kase)
  48. {
  49. int n,m,i,j;
  50. int u[10010],v[10010];
  51. scanf("%d %d",&n,&m);
  52. int sum=0;
  53. initialize(2*n);
  54. for(i=1;i<=n;i++)
  55. {
  56. scanf("%d",&total[i]);
  57. // total[i]=money[i];
  58. sum+=total[i];
  59. }
  60. for(i=0;i<m;i++)
  61. {
  62. scanf("%d %d",&u[i],&v[i]);
  63. }
  64. if(sum%n!=0)
  65. {
  66. printf("Case %d: No\n",kase);
  67. }
  68. else
  69. {
  70. int xx=sum/n;
  71. for(i=0;i<m;i++)
  72. {
  73. weighted_union(u[i],v[i]);
  74. }
  75. int prime=0;
  76. for(i=1;i<=n;i++)
  77. {
  78. if(arr[i]==i)
  79. {
  80. // cout<<i<<" "<<arr[i]<<endl;
  81. if(total[i]%xx!=0)
  82. {
  83. printf("Case %d: No\n",kase);
  84. prime=1;
  85. break;
  86. }
  87. }
  88. }
  89. if(prime==0)
  90. {
  91. printf("Case %d: Yes\n",kase);
  92. }
  93. }
  94. memset(si,0,sizeof si);
  95. memset(arr,0,sizeof arr);
  96. memset(total,0,sizeof total);//case 6 e jhamela lgase
  97. kase++;
  98. }
  99. return 0;
  100. }
Add Comment
Please, Sign In to add comment