Source code for submission s922

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( visited[v] ) return 0;
  26. 	if( neighbours[v].size() == 1 && neighbours[v][0] == p ) return 1;
  27.  
  28. 	visited[v] = true;
  29. 	open[v] = true;
  30.  
  31. 	int sum = 0;
  32. 	for( size_t i = 0; i < neighbours[v].size(); i++ ) {
  33. 		if( neighbours[v][i] == p ) {
  34. 			continue;
  35. 		}
  36.  
  37. 		if( open[neighbours[v][i]] ) {
  38. 			sum++;
  39. 		} else  {
  40. 			sum += dsp( neighbours[v][i], v );
  41. 		}
  42. 	}
  43.  
  44. 	open[v] = false;
  45.  
  46. 	return sum;
  47. }
  48.  
  49. int main() {
  50. 	int n,m;
  51. 	while( scanf("%d %d", &n, &m) == 2 ) {
  52. 		neighbours.clear();
  53. 		visited.clear();
  54. 		open.clear();
  55.  
  56. 		for( int i = 0; i < m; i++ ) {
  57. 			int u,v;
  58. 			scanf( "%d %d", &u, &v );
  59.  
  60. 			neighbours[u].push_back(v);
  61. 			neighbours[v].push_back(u);
  62. 		}
  63.  
  64. 		bool found = false;
  65. 		for( int i = 0; i < m; i++ ) {
  66. 			if( dsp( i, -1 ) >= 4 ) {
  67. 				found = true;
  68. 				break;
  69. 			}
  70. 		}
  71.  
  72. 		if( found ) {
  73. 			printf( "YES\n" );
  74. 		} else {
  75. 			printf( "NO\n" );
  76. 		}
  77. 	}
  78.  
  79. 	return 0;
  80. }
  81.  

Diff to submission s891

fn.cpp

--- c5.s891.cteam018.fn.cpp.0.fn.cpp
+++ c5.s922.cteam018.fn.cpp.0.fn.cpp
@@ -23,8 +23,10 @@
 
 int dsp( int v, int p ) {
+        if( visited[v] ) return 0;
         if( neighbours[v].size() == 1 && neighbours[v][0] == p ) return 1;
-        visited[v] = true;
 
+        visited[v] = true;
         open[v] = true;
+
         int sum = 0;
         for( size_t i = 0; i < neighbours[v].size(); i++ ) {
@@ -29,7 +31,11 @@
         int sum = 0;
         for( size_t i = 0; i < neighbours[v].size(); i++ ) {
+                if( neighbours[v][i] == p ) {
+                        continue;
+                }
+
                 if( open[neighbours[v][i]] ) {
                         sum++;
-                } else {
+                } else  {
                         sum += dsp( neighbours[v][i], v );
                 }
@@ -57,6 +64,8 @@
                 bool found = false;
                 for( int i = 0; i < m; i++ ) {
-                        if( visited[i] ) continue;
-                        if( dsp( i, -1 ) >= 4 ) found = true;
+                        if( dsp( i, -1 ) >= 4 ) {
+                                found = true;
+                                break;
+                        }
                 }