Source code for submission s733

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) pocet_trojek[komponenty[vrchol]]++;
  23.  
  24. for(int i = 0; i<hrany[vrchol].size(); i++){
  25. if(komponenty[hrany[vrchol][i]]==-1){
  26.  
  27. komponenty[hrany[vrchol][i]] = komponent;
  28. spust(hrany[vrchol][i]);
  29. }
  30.  
  31. }
  32.  
  33. }
  34.  
  35. bool over(int vrchol){
  36. set<int> mn;
  37. for(int i= 0; i<hrany[vrchol].size(); i++){
  38. for(int j = 0; j < hrany[vrchol][i]; j++){
  39. int v = hrany[vrchol][i];
  40. if(hrany[hrany[v][j]].size() == 3 && hrany[v][j]!=vrchol){
  41. mn.insert(hrany[v][j]);
  42. }
  43. }
  44. }
  45.  
  46. if(pocet_trojek[komponenty[vrchol]] - 1 - mn.size() > 0) return true;
  47. }
  48.  
  49. int main () {
  50. while(scanf("%d%d",&n,&m)!= EOF){
  51. hrany.clear();
  52. hrany.resize(n);
  53. komponenty.clear();
  54. komponenty.resize(n,-1);
  55. pocet_trojek.clear();
  56. pocet_trojek.resize(n,0);
  57. while(m--){
  58. int a,b;
  59. scanf("%d%d",&a,&b);
  60. a--; b--;
  61.  
  62. hrany[a].push_back(b);
  63. hrany[b].push_back(a);
  64. }
  65. komponent = 1;
  66.  
  67. bool bolo = false;
  68. for(int i = 0; i<n; i++){
  69. if(hrany[i].size() >= 4) {
  70. cout<<"YES"<<endl;
  71. bolo = true;
  72. }
  73. }
  74.  
  75. if(bolo) continue;
  76.  
  77. for(int i = 0; i < n; i++){
  78. if(komponenty[i]==-1) {
  79. komponenty[i]=komponent;
  80. spust(i);
  81. komponent++;
  82. }
  83. }
  84.  
  85. bool dasa=false;
  86.  
  87. for(int i = 0; i < n; i++){
  88. if(pocet_trojek[komponenty[i]] > 1){
  89. if(over(i)){
  90. dasa=true;
  91. break;
  92. }
  93. }
  94. }
  95.  
  96. if(dasa) cout<<"YES"<<endl;
  97. else cout<<"NO"<<endl;
  98. }
  99.  
  100.  
  101. }

Diff to submission s705

fn.cpp

--- c5.s705.cteam090.fn.cpp.0.fn.cpp
+++ c5.s733.cteam090.fn.cpp.0.fn.cpp
@@ -36,5 +36,10 @@
   set<int> mn;
   for(int i= 0; i<hrany[vrchol].size(); i++){
-    if(hrany[hrany[vrchol][i]].size()==3) mn.insert(hrany[vrchol][i]);
+    for(int j = 0; j < hrany[vrchol][i]; j++){
+      int v = hrany[vrchol][i];
+      if(hrany[hrany[v][j]].size() == 3 && hrany[v][j]!=vrchol){
+        mn.insert(hrany[v][j]);
+      }
+    }
   }