Source code for submission s1130

Go to diff to previous submission

fn.cpp

  1. //
  2. // File: fs.cc
  3. // Author: cteam008
  4. //
  5. // Created on October 19, 2013, 10:50 AM
  6. //
  7.  
  8. #include <stdlib.h>
  9. #include <stdio.h>
  10. #include <iostream>
  11. #include <vector>
  12. #include <queue>
  13.  
  14. using namespace std;
  15.  
  16.  
  17. //
  18. //
  19. //
  20. int main(int argc, char** argv) {
  21. int n, m, x, y;
  22. vector<int> deg3;
  23. bool isDeg4, same;
  24. while (cin >> n >> m) {
  25. vector<int> edges[n+1];
  26. int deg[n+1];
  27. for (int i = 0; i <= n; i++) {
  28. deg[i] = 0;
  29. }
  30. deg3.clear();
  31. isDeg4 = false;
  32. for (int i = 0; i < m; i++) {
  33. cin >> x >> y;
  34. deg[x]++;
  35. if (deg[x] >= 4) {
  36. isDeg4 = true;
  37. } else {
  38. if (deg[x] == 3) {
  39. deg3.push_back(x);
  40. }
  41. edges[x].push_back(y);
  42. }
  43. deg[y]++;
  44. if (deg[y] >= 4) {
  45. isDeg4 = true;
  46. } else {
  47. if (deg[y] == 3) {
  48. deg3.push_back(y);
  49. }
  50. edges[y].push_back(x);
  51. }
  52. }
  53. if (isDeg4) {
  54. cout << "YES" << endl;
  55. continue;
  56. }
  57. if (deg3.size() < 2) {
  58. cout << "NO" << endl;
  59. continue;
  60. }
  61. for (int i = 1; i < deg3.size(); i++) {
  62. vector<bool> used(n+1, false);
  63. x = deg3[i];
  64. used[x]=true;
  65. queue<int> fifo;
  66. for (int j = 0; j < 3; j++) {
  67. y =edges[x][j];
  68. if (deg[y] == 2) {
  69. used[y]=true;
  70. y = (edges[y][0] == x) ? edges[y][1] : edges[y][0];
  71. }
  72. if (deg[y] == 3) {
  73. same = false;
  74. for (int h = 0; h < 3; h++) {
  75. if (!used[edges[x][h]]) {
  76. for (int k = 0; k < 3; k++) {
  77. if (edges[x][h]==edges[y][k]) {
  78. same = true;
  79. break;
  80. }
  81. }
  82. }
  83. if (same) break;
  84. }
  85. if (!same) {
  86. isDeg4 = true;
  87. break;
  88. }
  89. fifo.push(y);
  90. } else if (deg[y] > 1) {
  91. fifo.push(y);
  92. }
  93. used[y]=true;
  94. }
  95. if (isDeg4) {
  96. break;
  97. }
  98. while (!fifo.empty()) {
  99. x = fifo.front();
  100. fifo.pop();
  101. for (int j = 0; j < deg[x]; j++) {
  102. y = edges[x][j];
  103. if (!used[y]) {
  104. if (deg[y] == 3) {
  105. isDeg4 = true;
  106. break;
  107. }
  108. fifo.push(y);
  109. }
  110.  
  111. }
  112. if (isDeg4) {
  113. break;
  114. }
  115. }
  116.  
  117. }
  118. if (isDeg4) {
  119. cout << "YES" << endl;
  120. } else {
  121. cout << "NO" << endl;
  122. }
  123. }
  124. return (EXIT_SUCCESS);
  125. }
  126.  

Diff to submission s1048

fn.cpp

--- c5.s1048.cteam008.fn.cpp.0.fn.cpp
+++ c5.s1130.cteam008.fn.cpp.0.fn.cpp
@@ -19,5 +19,5 @@
 //
 int main(int argc, char** argv) {
-    int n, m, x, y, z;
+    int n, m, x, y;
     vector<int> deg3;
     bool isDeg4, same;
@@ -66,27 +66,12 @@
             for (int j = 0; j < 3; j++) {
                 y =edges[x][j];
+                if (deg[y] == 2) {
+                    used[y]=true;
+                    y = (edges[y][0] == x) ? edges[y][1] : edges[y][0];
+                }
                 if (deg[y] == 3) {
                     same = false;
                     for (int h = 0; h < 3; h++) {
-                        for (int k = 0; k < 3; k++) {
-                            if (edges[x][h]==edges[y][k]) {
-                                same = true;
-                                break;
-                            }
-                        }
-                        if (same) break;
-                    }
-                    if (!same) {
-                        isDeg4 = true;
-                        break;
-                    }
-                    used[y]=true;
-                    fifo.push(y);
-                } else if (deg[y] == 2) {
-                    used[y]=true;
-                    y = (edges[y][0] == x) ? edges[y][1] : edges[y][0];
-                    if (deg[y] == 3) {
-                        same = false;
-                        for (int h = 0; h < 3; h++) {
+                        if (!used[edges[x][h]]) {
                             for (int k = 0; k < 3; k++) {
                                 if (edges[x][h]==edges[y][k]) {
@@ -95,16 +80,16 @@
                                 }
                             }
-                            if (same) break;
-                        }
-                        if (!same) {
-                            isDeg4 = true;
-                            break;
                         }
+                        if (same) break;
                     }
-                    used[y]=true;
-                    if (deg[y] > 1) {
-                        fifo.push(y);
+                    if (!same) {
+                        isDeg4 = true;
+                        break;
                     }
+                    fifo.push(y);
+                } else if (deg[y] > 1) {
+                    fifo.push(y);
                 }
+                used[y]=true;
             }
             if (isDeg4) {
@@ -132,11 +117,8 @@
         }
         if (isDeg4) {
-            cout << "YES" << endl;
-            
+            cout << "YES" << endl;           
         } else {
             cout << "NO" << endl;
-        }
-        
-        
+        }    
     }
     return (EXIT_SUCCESS);