Source code for submission s870

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 dvojica(int u, int v){
  40. set<int> mnD;
  41. for(int i = 0; i<hrany[u].size(); i++){
  42. if(hrany[u][i]!=v)
  43. mnD.insert(hrany[u][i]);
  44. }
  45. for(int i = 0; i<hrany[v].size(); i++){
  46. if(hrany[v][i]!=u)
  47. mnD.insert(hrany[v][i]);
  48. }
  49.  
  50. if(mnD.size()>=4) return false;
  51. else return true;
  52. }
  53.  
  54. bool over(int vrchol){
  55. multiset<int> mn;
  56. for(int i= 0; i<hrany[vrchol].size(); i++){
  57. for(int j = 0; j < hrany[hrany[vrchol][i]].size(); j++){
  58. int v = hrany[vrchol][i];
  59. if(hrany[hrany[v][j]].size() == 3 && hrany[v][j]!=vrchol){
  60. mn.insert(hrany[v][j]);
  61. }
  62. }
  63. }
  64.  
  65. multiset<int>::iterator it = mn.begin();
  66.  
  67. set<int> mnFin;
  68.  
  69. while(it!=mn.end()){
  70. if(mn.count(*it)>=2) mnFin.insert(*it);
  71. it++;
  72. }
  73.  
  74. for(int i=0; i< hrany[vrchol].size(); i++){
  75. int v = hrany[vrchol][i];
  76. if(hrany[v].size()==3 && dvojica(v,vrchol)){
  77. mnFin.insert(v);
  78. }
  79. }
  80.  
  81. /*if (vrchol==2){
  82.  
  83.   cout<<vrchol<<endl;
  84.   cout<<hrany[vrchol].size()<<endl;
  85.   cout<<pocet_trojek[komponenty[vrchol]]<<endl;
  86.   cout<<mn.size()<<endl;
  87.   cout<<mnFin.size()<<endl;
  88.   }*/
  89.  
  90. if(pocet_trojek[komponenty[vrchol]] - 1 - mnFin.size() > 0) {
  91. /* cout<<vrchol<<endl;
  92.   cout<<hrany[vrchol].size()<<endl;
  93.   cout<<pocet_trojek[komponenty[vrchol]]<<endl;
  94.   cout<<mn.size()<<endl;
  95.   cout<<mnFin.size()<<endl;*/
  96. return true;
  97.  
  98. }
  99. else return false;
  100. }
  101.  
  102. int main () {
  103. while(scanf("%d%d",&n,&m)!= EOF){
  104. hrany.clear();
  105. hrany.resize(n);
  106. komponenty.clear();
  107. komponenty.resize(n,-1);
  108. pocet_trojek.clear();
  109. pocet_trojek.resize(n+5,0);
  110. while(m--){
  111. int a,b;
  112. scanf("%d%d",&a,&b);
  113. a--; b--;
  114.  
  115. hrany[a].push_back(b);
  116. hrany[b].push_back(a);
  117. }
  118. komponent = 1;
  119.  
  120. bool bolo = false;
  121. for(int i = 0; i<n; i++){
  122. if(hrany[i].size() >= 4) {
  123. cout<<"YES"<<endl;
  124. bolo = true;
  125. }
  126. }
  127.  
  128. if(bolo) continue;
  129.  
  130. for(int i = 0; i < n; i++){
  131. if(komponenty[i]==-1) {
  132. komponenty[i]=komponent;
  133. spust(i);
  134. komponent++;
  135. }
  136. }
  137.  
  138. bool dasa=false;
  139.  
  140. for(int i = 0; i < n; i++){
  141. if(pocet_trojek[komponenty[i]] > 1){
  142. if(hrany[i].size()>=3 && over(i)){
  143. dasa=true;
  144. break;
  145. }
  146. }
  147. }
  148.  
  149. if(dasa) cout<<"YES"<<endl;
  150. else cout<<"NO"<<endl;
  151. }
  152.  
  153.  
  154. }

Diff to submission s818

fn.cpp

--- c5.s818.cteam090.fn.cpp.0.fn.cpp
+++ c5.s870.cteam090.fn.cpp.0.fn.cpp
@@ -37,6 +37,21 @@
 }    
 
+bool dvojica(int u, int v){
+  set<int> mnD;
+  for(int i = 0; i<hrany[u].size(); i++){
+    if(hrany[u][i]!=v)
+      mnD.insert(hrany[u][i]);
+  }
+  for(int i = 0; i<hrany[v].size(); i++){
+    if(hrany[v][i]!=u)
+      mnD.insert(hrany[v][i]);
+  }
+  
+  if(mnD.size()>=4) return false; 
+  else return true;
+}
+
 bool over(int vrchol){
-  set<int> mn;
+  multiset<int> mn;
   for(int i= 0; i<hrany[vrchol].size(); i++){
     for(int j = 0; j < hrany[hrany[vrchol][i]].size(); j++){
@@ -48,8 +63,35 @@
   }
   
-  if(pocet_trojek[komponenty[vrchol]] - 1 - mn.size() >= 0) {
-   // cout<<vrchol<<endl;
-    //cout<<pocet_trojek[komponenty[vrchol]]<<endl;
-    //cout<<mn.size()<<endl;
+  multiset<int>::iterator it = mn.begin();
+  
+  set<int> mnFin;
+  
+  while(it!=mn.end()){
+    if(mn.count(*it)>=2) mnFin.insert(*it);
+    it++;
+  }
+  
+  for(int i=0; i< hrany[vrchol].size(); i++){
+    int v = hrany[vrchol][i];
+    if(hrany[v].size()==3 && dvojica(v,vrchol)){
+      mnFin.insert(v);
+    }
+  }
+  
+  /*if (vrchol==2){
+    
+    cout<<vrchol<<endl;
+    cout<<hrany[vrchol].size()<<endl;
+    cout<<pocet_trojek[komponenty[vrchol]]<<endl;
+    cout<<mn.size()<<endl;
+    cout<<mnFin.size()<<endl;
+  }*/
+  
+  if(pocet_trojek[komponenty[vrchol]] - 1 - mnFin.size() > 0) {
+   /* cout<<vrchol<<endl;
+    cout<<hrany[vrchol].size()<<endl;
+    cout<<pocet_trojek[komponenty[vrchol]]<<endl;
+    cout<<mn.size()<<endl;
+    cout<<mnFin.size()<<endl;*/
     return true;
     
@@ -98,5 +140,5 @@
       for(int i = 0; i < n; i++){
         if(pocet_trojek[komponenty[i]] > 1){
-          if(over(i)){
+          if(hrany[i].size()>=3 && over(i)){
             dasa=true;
             break;