Source code for submission s819

Go to diff to previous submission

fn.cpp

  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <cmath>
  5. #include <set>
  6. #include <map>
  7. #include <string>
  8.  
  9. using namespace std;
  10.  
  11. vector< vector<int> > G;
  12. bool marked[1000000];
  13. bool ok = false;
  14. int good;
  15. int visited;
  16.  
  17. void dfs(int v)
  18. {
  19. 	if(G[v].size() >= 4)
  20. 		ok = true;
  21. 	else if(G[v].size() == 3)
  22. 		good++;
  23.  
  24. 	visited++;
  25. 	marked[v] = true;
  26.  
  27. 	for(int i=0; i<G[v].size(); i++)
  28. 	{
  29. 		int u = G[v][i];
  30. 		if(marked[u])
  31. 			continue;
  32. 		dfs(u);
  33. 	}
  34. }
  35.  
  36. int main()
  37. {
  38. 	int N, M;
  39. 	while(scanf("%d %d", &N, &M) == 2)
  40. 	{
  41. 		G = vector< vector<int> >(N);
  42. 		for(int i=0; i<N; i++)
  43. 		{
  44. 			G[i] = vector<int>();
  45. 			marked[i] = false;
  46. 		}
  47. 		for(int i=0; i<M; i++)
  48. 		{
  49. 			int x, y;
  50. 			scanf("%d %d", &x, &y);
  51. 			--x;
  52. 			--y;
  53. 			G[x].push_back(y);
  54. 			G[y].push_back(x);
  55. 		}
  56. 		ok = false;
  57. 		for(int i=0; !ok && i<N; i++)
  58. 		{
  59. 			visited = 0;
  60. 			good = 0;
  61. 			if(!marked[i])
  62. 				dfs(i);
  63. 			if(good >= 2 && visited >= 5)
  64. 				ok = true;
  65. 		}
  66. 		if(!ok)
  67. 			puts("NO");
  68. 		else
  69. 			puts("YES");
  70. 	}
  71.  
  72. 	return 0;	
  73. }
  74.  

Diff to submission s798

fn.cpp

--- c5.s798.cteam036.fn.cpp.0.fn.cpp
+++ c5.s819.cteam036.fn.cpp.0.fn.cpp
@@ -13,4 +13,5 @@
 bool ok = false;
 int good;
+int visited;
 
 void dfs(int v)
@@ -21,13 +22,8 @@
                 good++;
         
-        if(good == 2)
-                ok = true;
-                
-        if(ok)
-                return;
-        
+        visited++;
         marked[v] = true;
 
-        for(int i=0; !ok && i<G[v].size(); i++)
+        for(int i=0; i<G[v].size(); i++)
         {
                 int u = G[v][i];
@@ -61,7 +57,10 @@
                 for(int i=0; !ok && i<N; i++)
                 {
+                        visited = 0;
                         good = 0;
                         if(!marked[i])
                                 dfs(i);
+                        if(good >= 2 && visited >= 5)
+                                ok = true;
                 }
                 if(!ok)