Source code for submission s891

Go to diff to previous submission

fn.cpp

  1. #include <iostream>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <string>
  7. #include <list>
  8. #include <map>
  9. #include <queue>
  10. #include <set>
  11. #include <sstream>
  12. #include <stack>
  13. #include <utility>
  14. #include <vector>
  15.  
  16. using namespace std;
  17.  
  18. #define DEBUG(x) cout << ">>> " #x << " : " << x << endl;
  19.  
  20. map<int,vector<int> > neighbours;
  21. map<int,bool> visited;
  22. map<int,bool> open;
  23.  
  24. int dsp( int v, int p ) {
  25. if( neighbours[v].size() == 1 && neighbours[v][0] == p ) return 1;
  26. visited[v] = true;
  27.  
  28. open[v] = true;
  29. int sum = 0;
  30. for( size_t i = 0; i < neighbours[v].size(); i++ ) {
  31. if( open[neighbours[v][i]] ) {
  32. sum++;
  33. } else {
  34. sum += dsp( neighbours[v][i], v );
  35. }
  36. }
  37. open[v] = false;
  38.  
  39. return sum;
  40. }
  41.  
  42. int main() {
  43. int n,m;
  44. while( scanf("%d %d", &n, &m) == 2 ) {
  45. neighbours.clear();
  46. visited.clear();
  47. open.clear();
  48.  
  49. for( int i = 0; i < m; i++ ) {
  50. int u,v;
  51. scanf( "%d %d", &u, &v );
  52.  
  53. neighbours[u].push_back(v);
  54. neighbours[v].push_back(u);
  55. }
  56.  
  57. bool found = false;
  58. for( int i = 0; i < m; i++ ) {
  59. if( visited[i] ) continue;
  60. if( dsp( i, -1 ) >= 4 ) found = true;
  61. }
  62.  
  63. if( found ) {
  64. printf( "YES\n" );
  65. } else {
  66. printf( "NO\n" );
  67. }
  68. }
  69.  
  70. return 0;
  71. }
  72.  

Diff to submission s687

fn.cpp

--- c5.s687.cteam018.fn.cpp.0.fn.cpp
+++ c5.s891.cteam018.fn.cpp.0.fn.cpp
@@ -18,13 +18,32 @@
 #define DEBUG(x) cout << ">>> " #x << " : " << x << endl;
 
+map<int,vector<int> > neighbours;
+map<int,bool> visited;
+map<int,bool> open;
+
+int dsp( int v, int p ) {
+        if( neighbours[v].size() == 1 && neighbours[v][0] == p ) return 1;
+        visited[v] = true;
+
+        open[v] = true;
+        int sum = 0;
+        for( size_t i = 0; i < neighbours[v].size(); i++ ) {
+                if( open[neighbours[v][i]] ) {
+                        sum++;
+                } else {
+                        sum += dsp( neighbours[v][i], v );
+                }
+        }
+        open[v] = false;
+
+        return sum;
+}
+
 int main() {
         int n,m;
         while( scanf("%d %d", &n, &m) == 2 ) {
-                map<int,int> neighbours;
-                bool found = false;
-
-                for( int i = 0; i < n; i++ ) {
-                        neighbours[i] = 0;
-                }
+                neighbours.clear();
+                visited.clear();
+                open.clear();
 
                 for( int i = 0; i < m; i++ ) {
@@ -32,6 +51,12 @@
                         scanf( "%d %d", &u, &v );
 
-                        if( ++neighbours[u] >= 4 ) { found = true; }
-                        if( ++neighbours[v] >= 4 ) { found = true; }
+                        neighbours[u].push_back(v);
+                        neighbours[v].push_back(u);
+                }
+
+                bool found = false;
+                for( int i = 0; i < m; i++ ) {
+                        if( visited[i] ) continue;
+                        if( dsp( i, -1 ) >= 4 ) found = true;
                 }