Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int arr[2000];
- int si[2000];
- int total[2000];
- void initialize(int N)
- {
- for(int i=0;i<=N;i++)
- {
- arr[i]=i;
- si[i]=1;
- }
- return;
- }
- int root(int i)
- {
- while(i!=arr[i])
- {
- i=arr[i];
- }
- return i;
- }
- void weighted_union(int A,int B)
- {
- int root_A=root(A);
- int root_B=root(B);
- if(si[root_A]<si[root_B])
- {
- arr[root_A]=arr[root_B];
- si[root_B]+=si[root_A];
- total[root_B]+=total[root_A];
- return;
- }
- else
- {
- arr[root_B]=arr[root_A];
- si[root_A]+=si[root_B];
- total[root_A]+=total[root_B];
- return;
- }
- }
- int main()
- {
- int t,kase=1;
- scanf("%d",&t);
- while(t>=kase)
- {
- int n,m,i,j;
- int u[10010],v[10010];
- scanf("%d %d",&n,&m);
- int sum=0;
- initialize(2*n);
- for(i=1;i<=n;i++)
- {
- scanf("%d",&total[i]);
- // total[i]=money[i];
- sum+=total[i];
- }
- for(i=0;i<m;i++)
- {
- scanf("%d %d",&u[i],&v[i]);
- }
- if(sum%n!=0)
- {
- printf("Case %d: No\n",kase);
- }
- else
- {
- int xx=sum/n;
- for(i=0;i<m;i++)
- {
- weighted_union(u[i],v[i]);
- }
- int prime=0;
- for(i=1;i<=n;i++)
- {
- if(arr[i]==i)
- {
- // cout<<i<<" "<<arr[i]<<endl;
- if(total[i]%xx!=0)
- {
- printf("Case %d: No\n",kase);
- prime=1;
- break;
- }
- }
- }
- if(prime==0)
- {
- printf("Case %d: Yes\n",kase);
- }
- }
- memset(si,0,sizeof si);
- memset(arr,0,sizeof arr);
- memset(total,0,sizeof total);//case 6 e jhamela lgase
- kase++;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment