Source code for submission s1048

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, z;
  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] == 3) {
  69. same = false;
  70. for (int h = 0; h < 3; h++) {
  71. for (int k = 0; k < 3; k++) {
  72. if (edges[x][h]==edges[y][k]) {
  73. same = true;
  74. break;
  75. }
  76. }
  77. if (same) break;
  78. }
  79. if (!same) {
  80. isDeg4 = true;
  81. break;
  82. }
  83. used[y]=true;
  84. fifo.push(y);
  85. } else if (deg[y] == 2) {
  86. used[y]=true;
  87. y = (edges[y][0] == x) ? edges[y][1] : edges[y][0];
  88. if (deg[y] == 3) {
  89. same = false;
  90. for (int h = 0; h < 3; h++) {
  91. for (int k = 0; k < 3; k++) {
  92. if (edges[x][h]==edges[y][k]) {
  93. same = true;
  94. break;
  95. }
  96. }
  97. if (same) break;
  98. }
  99. if (!same) {
  100. isDeg4 = true;
  101. break;
  102. }
  103. }
  104. used[y]=true;
  105. if (deg[y] > 1) {
  106. fifo.push(y);
  107. }
  108. }
  109. }
  110. if (isDeg4) {
  111. break;
  112. }
  113. while (!fifo.empty()) {
  114. x = fifo.front();
  115. fifo.pop();
  116. for (int j = 0; j < deg[x]; j++) {
  117. y = edges[x][j];
  118. if (!used[y]) {
  119. if (deg[y] == 3) {
  120. isDeg4 = true;
  121. break;
  122. }
  123. fifo.push(y);
  124. }
  125.  
  126. }
  127. if (isDeg4) {
  128. break;
  129. }
  130. }
  131.  
  132. }
  133. if (isDeg4) {
  134. cout << "YES" << endl;
  135.  
  136. } else {
  137. cout << "NO" << endl;
  138. }
  139.  
  140.  
  141. }
  142. return (EXIT_SUCCESS);
  143. }
  144.  

Diff to submission s1000

fn.cpp

--- c5.s1000.cteam008.fn.cpp.0.fn.cpp
+++ c5.s1048.cteam008.fn.cpp.0.fn.cpp
@@ -86,20 +86,24 @@
                     used[y]=true;
                     y = (edges[y][0] == x) ? edges[y][1] : edges[y][0];
-                    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 (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;
                         }
-                        if (same) break;
-                    }
-                    if (!same) {
-                        isDeg4 = true;
-                        break;
                     }
                     used[y]=true;
-                    fifo.push(y);
+                    if (deg[y] > 1) {
+                        fifo.push(y);
+                    }
                 }
             }