Source code for submission s516

Go to diff to previous submission

fn.cpp

  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4.  
  5. #include<cmath>
  6. #include<cctype>
  7. #include<climits>
  8. #include<algorithm>
  9. #include<utility>
  10. #include<string>
  11.  
  12. #include<deque>
  13. #include<list>
  14. #include<map>
  15. #include<queue>
  16. #include<set>
  17. #include<stack>
  18. #include<vector>
  19.  
  20.  
  21. using namespace std;
  22.  
  23. #define REP(i,N) for (int i = 0; i < (N); i++)
  24. #define FOR(i,a,b) for (int i = (a); i <= (b); i++)
  25. #define FORI(i,a,b) for (int i = (a); i < (b); i++)
  26. #define FORD(i,a,b) for (int i = (a)-1; i >= (b); i--)
  27. #define DP(arg...) fprintf(stderr, ## arg)
  28.  
  29. typedef long long ll;
  30. typedef long double ld;
  31. typedef pair<int,int> ii;
  32.  
  33. int N,M;
  34. vector<int> E[11000];
  35. int deg[11000];
  36. int vis[11000];
  37. int d3, d4;
  38.  
  39. void dfs(int v) {
  40. 	//DP("%d ", v);
  41. 		if (deg[v] >= 3) d3++;
  42. 		if (deg[v] >= 4) d4++;
  43. 		vis[v] = 1;
  44. 		REP(i,E[v].size()) {
  45. 			if (!vis[E[v][i]])
  46. 				dfs(E[v][i]);
  47. 		}
  48. }
  49.  
  50. void solve() {
  51. 	REP(i,N) { deg[i] = 0; E[i].clear(); vis[i] = 0; }
  52. 	REP(i,M) { int a,b;
  53. 			scanf("%d%d", &a, &b);
  54. 			a--; b--;
  55. 			deg[a]++; deg[b]++;
  56. 			E[a].push_back(b);
  57. 			E[b].push_back(a);
  58.  
  59. 	}
  60. 	REP(k,N) {
  61. 				d3 = 0, d4 = 0;
  62. 				if (!vis[k]) dfs(k);
  63. 				if (d3 >= 2 || d4 >= 1) { printf("YES\n"); return; }
  64. 	}
  65. 	printf("NO\n");
  66.  
  67. }
  68.  
  69. int main() {
  70. 	while (scanf("%d%d", &N, &M) != EOF) {
  71. 		solve();
  72. 	}
  73. 	return 0;
  74. }
  75.  

Diff to submission s453

fn.cpp

--- c5.s453.cteam022.fn.cpp.0.fn.cpp
+++ c5.s516.cteam022.fn.cpp.0.fn.cpp
@@ -32,14 +32,35 @@
 
 int N,M;
-//vector<int> E[11000];
+vector<int> E[11000];
 int deg[11000];
+int vis[11000];
+int d3, d4;
+
+void dfs(int v) {
+        //DP("%d ", v);
+                if (deg[v] >= 3) d3++;
+                if (deg[v] >= 4) d4++;
+                vis[v] = 1;
+                REP(i,E[v].size()) {
+                        if (!vis[E[v][i]])
+                                dfs(E[v][i]);
+                }
+}
 
 void solve() {
-        REP(i,N) deg[i] = 0;
+        REP(i,N) { deg[i] = 0; E[i].clear(); vis[i] = 0; }
         REP(i,M) { int a,b;
-                        scanf("%d%d", &a, &b); deg[a-1]++; deg[b-1]++;
-        
+                        scanf("%d%d", &a, &b);
+                        a--; b--;
+                        deg[a]++; deg[b]++;
+                        E[a].push_back(b);
+                        E[b].push_back(a);
+                        
+        }
+        REP(k,N) {
+                                d3 = 0, d4 = 0;
+                                if (!vis[k]) dfs(k);
+                                if (d3 >= 2 || d4 >= 1) { printf("YES\n"); return; }
         }
-        REP(i,N) { if (deg[i] >= 4) { printf("YES\n"); return; } }
         printf("NO\n");