Advertisement
Saleh127

Light oj(LO) 1263

Feb 4th, 2021
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.40 KB | None | 0 0
  1. ///Light oj 1263
  2. ///DFS and math
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define ll long long
  6. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  7.  
  8. vector<ll>g[10000];
  9. bool v[10000];
  10. ll x=0,y=0,c[10000];
  11.  
  12. void dfs(ll nd)
  13. {
  14. if(v[nd]==1) return;
  15.  
  16. x+=c[nd];
  17. y++;
  18. v[nd]=1;
  19.  
  20. for(ll i=0; i<g[nd].size(); i++)
  21. {
  22. if(v[g[nd][i]]==0)
  23. {
  24. dfs(g[nd][i]);
  25. }
  26. }
  27. }
  28.  
  29. int main()
  30. {
  31. ios_base::sync_with_stdio(0);
  32. cin.tie(0);
  33. cout.tie(0);
  34.  
  35. test
  36. {
  37. ll a,b,n,m,i,j,k=0,l=0;
  38.  
  39. cin>>n>>m;
  40.  
  41. for(i=0; i<n+10; i++)
  42. {
  43. g[i].clear();
  44. v[i]=0;
  45. c[i]=0;
  46. }
  47.  
  48. for(i=1; i<=n; i++)
  49. {
  50. cin>>c[i];
  51. k+=c[i];
  52.  
  53. }
  54.  
  55. for(i=0; i<m; i++)
  56. {
  57. cin>>a>>b;
  58. g[a].push_back(b);
  59. g[b].push_back(a);
  60. }
  61.  
  62. ll av=k/n;
  63.  
  64. for(i=1; i<=n; i++)
  65. {
  66. x=0;
  67. y=0;
  68. if(v[i]==0)
  69. {
  70. dfs(i);
  71. }
  72. if(x!=(y*av))
  73. {
  74. l=1;
  75. break;
  76. }
  77. }
  78.  
  79. cout<<"Case "<<cs<<": ";
  80.  
  81. if(l==0)
  82. {
  83. cout<<"Yes"<<endl;
  84. }
  85. else cout<<"No"<<endl;
  86. }
  87.  
  88.  
  89. return 0;
  90. }
  91.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement