Source code for submission s837

Go to diff to previous submission

fn.cpp

  1. #include <stdio.h>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. vector <int> v;
  7. vector <int> un;
  8. vector <int> vysl;
  9. vector <int> velk;
  10.  
  11. int find(int a){
  12.  
  13. while(un[a]!=a){
  14. a = un[a];
  15. }
  16.  
  17. return a;
  18. }
  19.  
  20. void uni(int a, int b){
  21. int aa = find(a);
  22. int bb = find(b);
  23.  
  24. if(aa!=bb){
  25. if(velk[aa] <= velk[bb]){
  26. un[aa] = bb;
  27. velk[bb] += velk[aa];
  28. }
  29. else{
  30. un[bb] = aa;
  31. velk[aa] += velk[bb];
  32. }
  33.  
  34. }
  35.  
  36. }
  37.  
  38. int connected(int a, int b){
  39. int aa = find(a);
  40. int bb = find(b);
  41.  
  42. if(aa == bb) return 1;
  43. else return 0;
  44.  
  45. }
  46.  
  47.  
  48.  
  49.  
  50. int main(){
  51.  
  52. int n,m,a,b;
  53.  
  54. while(scanf("%d %d", &n,&m) == 2){
  55. int uspech = 0;
  56.  
  57. v.clear();
  58. un.clear();
  59. vysl.clear();
  60. velk.clear();
  61.  
  62. //vector<int> h(n);
  63.  
  64. for(int i=0; i<n; i++){
  65. v.push_back(0);
  66. un.push_back(i);
  67. vysl.push_back(0);
  68. velk.push_back(1);
  69. //h[i]=0;
  70. }
  71.  
  72. for(int i = 0; i<m; i++){
  73. scanf("%d %d", &a,&b);
  74. a--;
  75. b--;
  76.  
  77. if(connected(a,b) == 0){
  78.  
  79. v[a]++;
  80. v[b]++;
  81.  
  82. uni(a,b);
  83.  
  84. }
  85. //else {printf ("SPOJENE\n");}
  86. }
  87.  
  88. for(int i=0; i<n; i++){
  89. int koren;
  90.  
  91. if(v[i]==1){
  92. koren = find(i);
  93. vysl[koren]++;
  94. if(vysl[koren] >= 4){
  95. uspech = 1;
  96. break;
  97. }
  98. }
  99.  
  100.  
  101.  
  102. }
  103.  
  104. /*
  105.   printf("v: ");
  106.   for(int i=0; i<n; i++){
  107.   printf("%d ", v[i]);
  108.   }
  109.   printf("\n");
  110.  
  111.   printf("un: ");
  112.   for(int i=0; i<n; i++){
  113.   printf("%d ", un[i]);
  114.   }
  115.   printf("\n");
  116.  
  117.   printf("vysl: ");
  118.   for(int i=0; i<n; i++){
  119.   printf("%d ", vysl[i]);
  120.   }
  121.   printf("\n");
  122.   */
  123.  
  124. if(uspech == 1){
  125. printf("YES\n");
  126. }
  127. else
  128. {
  129. printf("NO\n");
  130. }
  131.  
  132. }
  133.  
  134. return 0;
  135. }
  136.  

Diff to submission s828

fn.cpp

--- c5.s828.cteam077.fn.cpp.0.fn.cpp
+++ c5.s837.cteam077.fn.cpp.0.fn.cpp
@@ -92,9 +92,11 @@
                                 koren = find(i);
                                 vysl[koren]++;
+                                if(vysl[koren] >= 4){
+                                        uspech = 1;
+                                        break;
+                                }
                         }
                         
-                        if(vysl[koren] >= 4){
-                                uspech = 1;
-                        }
+                        
                         
                 }