Source code for submission s1114

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. vector<int> good;
  15. int visited;
  16.  
  17. void tam(int v)
  18. {
  19. 	visited++;
  20. 	marked[v] = true;
  21.  
  22. 	for(int i=0; i<G[v].size(); i++)
  23. 	{
  24. 		int u = G[v][i];
  25. 		if(marked[u])
  26. 			continue;
  27. 		tam(u);
  28. 	}
  29. }
  30.  
  31. void zpet(int v)
  32. {
  33. 	visited++;
  34. 	marked[v] = false;
  35.  
  36. 	for(int i=0; i<G[v].size(); i++)
  37. 	{
  38. 		int u = G[v][i];
  39. 		if(!marked[u])
  40. 			continue;
  41. 		zpet(u);
  42. 	}
  43. }
  44.  
  45. void dfs(int v)
  46. {
  47. 	if(G[v].size() >= 4)
  48. 		ok = true;
  49. 	else if(G[v].size() == 3)
  50. 	{
  51. 		//printf("test %d\n", v);
  52. 		for(int i=0; !ok && i<good.size(); i++)
  53. 		{
  54. 			int u = good[i];
  55.  
  56. 			//printf("%d %d\n", v, u);
  57.  
  58. 			set<int> s;
  59. 			for(int j=0; j<G[v].size(); j++)
  60. 			{
  61. 				if(G[v][j] != u)
  62. 				{
  63. 					//printf("add %d\n", G[v][j]);
  64. 					s.insert(G[v][j]);
  65. 				}
  66. 			}
  67. 			int b = 0;
  68. 			for(int j=0; j<G[u].size(); j++)
  69. 			{
  70. 				if(G[u][j] != v)
  71. 				{
  72. 					//s.insert(G[u][j]);
  73. 					//printf("test %d\n", G[u][j]);
  74. 					if(s.count(G[u][j]) == 0)
  75. 						b++;
  76. 				}
  77. 			}
  78. 			if(b >= 2)
  79. 			{
  80. 				ok = true;
  81. 			}
  82. 			//printf("%d %d %d\n", v, u, b);
  83. 		}
  84. 		good.push_back(v);
  85. 	}
  86.  
  87. 	if(ok)
  88. 		return;
  89.  
  90. 	visited++;
  91. 	marked[v] = true;
  92.  
  93. 	for(int i=0; !ok && i< G[v].size(); i++)
  94. 	{
  95. 		int u = G[v][i];
  96. 		if(marked[u])
  97. 			continue;
  98. 		dfs(u);
  99. 	}
  100. }
  101.  
  102. int main()
  103. {
  104. 	int N, M;
  105. 	while(scanf("%d %d", &N, &M) == 2)
  106. 	{
  107. 		G = vector< vector<int> >(N);
  108. 		for(int i=0; i<N; i++)
  109. 		{
  110. 			G[i] = vector<int>();
  111. 			marked[i] = false;
  112. 		}
  113. 		for(int i=0; i<M; i++)
  114. 		{
  115. 			int x, y;
  116. 			scanf("%d %d", &x, &y);
  117. 			--x;
  118. 			--y;
  119. 			G[x].push_back(y);
  120. 			G[y].push_back(x);
  121. 		}
  122. 		ok = false;
  123. 		for(int i=0; !ok && i<N; i++)
  124. 		{
  125. 			visited = 0;
  126. 			good = vector<int>();
  127. 			if(!marked[i])
  128. 			{
  129. 				visited = 0;
  130. 				tam(i);
  131. 				//printf("tam from %d visited %d\n", i, visited);
  132. 				if(visited <= 4)
  133. 				{
  134. 					//printf("smula from %d visited %d\n", i, visited);
  135. 					continue;
  136. 				}
  137. 				visited = 0;
  138. 				zpet(i);
  139. 				//printf("zpet from %d visited %d\n", i, visited);
  140. 				visited = 0;
  141. 				dfs(i);
  142. 				//printf("dfs from %d visited %d\n", i, visited);
  143. 			}
  144. 		}
  145. 		if(!ok)
  146. 			puts("NO");
  147. 		else
  148. 			puts("YES");
  149. 	}
  150.  
  151. 	return 0;	
  152. }
  153.  

Diff to submission s1029

fn.cpp

--- c5.s1029.cteam036.fn.cpp.0.fn.cpp
+++ c5.s1114.cteam036.fn.cpp.0.fn.cpp
@@ -60,15 +60,25 @@
                         {
                                 if(G[v][j] != u)
+                                {
+                                        //printf("add %d\n", G[v][j]);
                                         s.insert(G[v][j]);
+                                }
                         }
+                        int b = 0;
                         for(int j=0; j<G[u].size(); j++)
                         {
                                 if(G[u][j] != v)
-                                        s.insert(G[u][j]);
+                                {
+                                        //s.insert(G[u][j]);
+                                        //printf("test %d\n", G[u][j]);
+                                        if(s.count(G[u][j]) == 0)
+                                                b++;
+                                }
                         }
-                        if(s.size() >= 4)
+                        if(b >= 2)
                         {
                                 ok = true;
                         }
+                        //printf("%d %d %d\n", v, u, b);
                 }
                 good.push_back(v);