Source code for submission s828

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.  			}
  95.  
  96.  			if(vysl[koren] >= 4){
  97.  				uspech = 1;
  98.  			}
  99.  
  100.  		}
  101.  
  102.  		/*
  103.  		printf("v: ");
  104.  		for(int i=0; i<n; i++){
  105.  			printf("%d ", v[i]);
  106.  		}
  107.  		printf("\n");
  108.  		
  109.  		printf("un: ");
  110.  		for(int i=0; i<n; i++){
  111.  			printf("%d ", un[i]);
  112.  		}
  113.  		printf("\n");
  114.  		
  115.  		printf("vysl: ");
  116.  		for(int i=0; i<n; i++){
  117.  			printf("%d ", vysl[i]);
  118.  		}
  119.  		printf("\n");
  120.  		*/
  121.  
  122.  		if(uspech == 1){
  123.  			printf("YES\n");
  124.  		}
  125.  		else
  126.  		{
  127.  			printf("NO\n");
  128.  		}
  129.  
  130. 	}
  131.  
  132. 	return 0;
  133. }
  134.  

Diff to submission s793

fn.cpp

--- c5.s793.cteam077.fn.cpp.0.fn.cpp
+++ c5.s828.cteam077.fn.cpp.0.fn.cpp
@@ -58,4 +58,5 @@
                 un.clear();
                 vysl.clear();
+                velk.clear();
                 
                 //vector<int> h(n);