Source code for submission s818

Go to diff to previous submission

fn.cpp

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7. #include <string>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <queue>
  11.  
  12. using namespace std;
  13.  
  14. int n,m;
  15.       int komponent = 1;
  16.  
  17.     vector<vector<int> >  hrany;
  18.     vector<int> komponenty;
  19.     vector<int> pocet_trojek;
  20.  
  21. void spust(int vrchol){
  22.   if(hrany[vrchol].size() == 3) {
  23.     //cout<<"tri u: "<<vrchol+1<<endl;
  24.     pocet_trojek[komponenty[vrchol]]++;
  25.  
  26.   }
  27.  
  28.   for(int i = 0; i<hrany[vrchol].size(); i++){
  29.     if(komponenty[hrany[vrchol][i]]==-1){
  30.  
  31. 	komponenty[hrany[vrchol][i]] = komponent;
  32. 	spust(hrany[vrchol][i]);
  33.     }
  34.  
  35.   }
  36.  
  37. }    
  38.  
  39. bool over(int vrchol){
  40.   set<int> mn;
  41.   for(int i= 0; i<hrany[vrchol].size(); i++){
  42.     for(int j = 0; j < hrany[hrany[vrchol][i]].size(); j++){
  43.       int v = hrany[vrchol][i];
  44.       if(hrany[hrany[v][j]].size() == 3 && hrany[v][j]!=vrchol){
  45. 	mn.insert(hrany[v][j]);
  46.       }
  47.     }
  48.   }
  49.  
  50.   if(pocet_trojek[komponenty[vrchol]] - 1 - mn.size() >= 0) {
  51.    // cout<<vrchol<<endl;
  52.     //cout<<pocet_trojek[komponenty[vrchol]]<<endl;
  53.     //cout<<mn.size()<<endl;
  54.     return true;
  55.  
  56.   }
  57.   else return false;
  58. }
  59.  
  60. int main () {
  61.   while(scanf("%d%d",&n,&m)!= EOF){
  62.     hrany.clear();
  63.     hrany.resize(n);
  64.     komponenty.clear();
  65.     komponenty.resize(n,-1);
  66.     pocet_trojek.clear();
  67.     pocet_trojek.resize(n+5,0);
  68.     while(m--){
  69.       int a,b;
  70.       scanf("%d%d",&a,&b);
  71.       a--; b--;
  72.  
  73.       hrany[a].push_back(b);
  74.       hrany[b].push_back(a);
  75.     }
  76.       komponent = 1;
  77.  
  78.       bool bolo = false;
  79.       for(int i = 0; i<n; i++){
  80. 	if(hrany[i].size() >= 4) {
  81. 	  cout<<"YES"<<endl;
  82. 	 bolo = true;
  83. 	}
  84.       }
  85.  
  86.       if(bolo) continue;
  87.  
  88.       for(int i = 0; i < n; i++){
  89. 	if(komponenty[i]==-1) {
  90. 	  komponenty[i]=komponent;
  91. 	  spust(i);
  92. 	  komponent++;
  93. 	}
  94.       }
  95.  
  96.       bool dasa=false;
  97.  
  98.       for(int i = 0; i < n; i++){
  99. 	if(pocet_trojek[komponenty[i]] > 1){
  100. 	  if(over(i)){
  101. 	    dasa=true;
  102. 	    break;
  103. 	  }
  104. 	}
  105.       }
  106.  
  107.       if(dasa) cout<<"YES"<<endl;
  108.       else cout<<"NO"<<endl;
  109.     }
  110.  
  111.  
  112. }

Diff to submission s755

fn.cpp

--- c5.s755.cteam090.fn.cpp.0.fn.cpp
+++ c5.s818.cteam090.fn.cpp.0.fn.cpp
@@ -20,5 +20,9 @@
 
 void spust(int vrchol){
-  if(hrany[vrchol].size() == 3) pocet_trojek[komponenty[vrchol]]++;
+  if(hrany[vrchol].size() == 3) {
+    //cout<<"tri u: "<<vrchol+1<<endl;
+    pocet_trojek[komponenty[vrchol]]++;
+    
+  }
   
   for(int i = 0; i<hrany[vrchol].size(); i++){
@@ -44,5 +48,12 @@
   }
   
-  if(pocet_trojek[komponenty[vrchol]] - 1 - mn.size() > 0) return true;
+  if(pocet_trojek[komponenty[vrchol]] - 1 - mn.size() >= 0) {
+   // cout<<vrchol<<endl;
+    //cout<<pocet_trojek[komponenty[vrchol]]<<endl;
+    //cout<<mn.size()<<endl;
+    return true;
+    
+  }
+  else return false;
 }