Source code for submission s793

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.  
  61. 		//vector<int> h(n);
  62.  
  63. 		for(int i=0; i<n; i++){
  64. 			v.push_back(0);
  65. 			un.push_back(i);
  66. 			vysl.push_back(0);
  67. 			velk.push_back(1);			
  68. 			//h[i]=0;
  69. 		}
  70.  
  71. 		for(int i = 0; i<m; i++){
  72. 			scanf("%d %d", &a,&b);
  73. 			a--;
  74. 			b--;
  75.  
  76. 			if(connected(a,b) == 0){
  77.  
  78. 				v[a]++;
  79. 				v[b]++;
  80.  
  81. 				uni(a,b);
  82.  
  83. 			}
  84. 			//else {printf ("SPOJENE\n");}
  85.  		}
  86.  
  87.  		for(int i=0; i<n; i++){
  88.  			int koren;
  89.  
  90.  			if(v[i]==1){
  91.  				koren = find(i);
  92.  				vysl[koren]++;
  93.  			}
  94.  
  95.  			if(vysl[koren] >= 4){
  96.  				uspech = 1;
  97.  			}
  98.  
  99.  		}
  100.  
  101.  		/*
  102.  		printf("v: ");
  103.  		for(int i=0; i<n; i++){
  104.  			printf("%d ", v[i]);
  105.  		}
  106.  		printf("\n");
  107.  		
  108.  		printf("un: ");
  109.  		for(int i=0; i<n; i++){
  110.  			printf("%d ", un[i]);
  111.  		}
  112.  		printf("\n");
  113.  		
  114.  		printf("vysl: ");
  115.  		for(int i=0; i<n; i++){
  116.  			printf("%d ", vysl[i]);
  117.  		}
  118.  		printf("\n");
  119.  		*/
  120.  
  121.  		if(uspech == 1){
  122.  			printf("YES\n");
  123.  		}
  124.  		else
  125.  		{
  126.  			printf("NO\n");
  127.  		}
  128.  
  129. 	}
  130.  
  131. 	return 0;
  132. }
  133.  

Diff to submission s760

fn.cpp

--- c5.s760.cteam077.fn.cpp.0.fn.cpp
+++ c5.s793.cteam077.fn.cpp.0.fn.cpp
@@ -36,4 +36,13 @@
 }
 
+int connected(int a, int b){
+        int aa = find(a);
+        int bb = find(b);
+        
+        if(aa == bb) return 1;
+        else return 0;
+
+}
+
 
 
@@ -65,8 +74,13 @@
                         b--;
                         
-                        v[a]++;
-                        v[b]++;
+                        if(connected(a,b) == 0){
                         
-                        uni(a,b);
+                                v[a]++;
+                                v[b]++;
+                                
+                                uni(a,b);
+                        
+                        }
+                        //else {printf ("SPOJENE\n");}
                 }